#hm-medium
TAOCP 3.4.1 Exercise 23
Section 3.4.1: Numerical Distributions Exercise 23. [ HM25 ] (J. von Neumann.) Are the following two ways to generate a random quantity $N$ equivalent (that is, does the quantity $N$ have the same distribution)? Method 1: Set $X \leftarrow \sin((\pi/2)U)$, where $U$ is uniform. Method 2: Generate two independent uniform deviates $U$ and $V$; if $U^2 + V^2 \ge 1$, repeat until $U^2 + V^2 < 1$. Then set $X...
TAOCP 3.4.1 Exercise 16
Section 3.4.1: Numerical Distributions Exercise 16. ▶ [ HM25 ] (J. H. Ahrens.) Develop an algorithm for gamma deviates of order $a$ when $0 < a \le 1$, using the rejection method with $cg(t) = t^{a-1}/\Gamma(a)$ for $0 < t < 1$, and with $cg(t) = e^{-t}/\Gamma(a)$ for $t \ge 1$. Verified: yes Solve time: 4m35s Solution Let $$ f(x)=\frac{x^{a-1}e^{-x}}{\Gamma(a)}, \qquad x>0,\qquad 0<a\le1, $$ be the gamma density of order...
TAOCP 3.4.1 Exercise 15
Section 3.4.1: Numerical Distributions Exercise 15. [ HM21 ] If $X_1$ and $X_2$ are independent random variables with the respective distributions $F_1(x)$ and $F_2(x)$, and with densities $f_1(x) = F_1'(x)$, $f_2(x) = F_2'(x)$, what are the distribution and density functions of the quantity $X_1 + X_2$? Verified: yes Solve time: 1m17s Solution Let $S=X_1+X_2.$ Since $X_1$ and $X_2$ are independent, the distribution function of $S$ is =\Pr{X_1+X_2\le x}.$$ Condition on...
TAOCP 3.4.1 Exercise 10
Section 3.4.1: Numerical Distributions Exercise 10. ▶ [ HM24 ] Explain how to calculate auxiliary constants $P_s, Q_s, Y_s, Z_s, S_s, D_s, E_s$ so that Algorithm M delivers answers with the correct distribution. Verified: no Solve time: 5m13s Solution Algorithm M is designed to generate a discrete random variable $$ X \in {x_0, x_1, \dots, x_{n-1}}, \quad \Pr{X = x_j} = p_j \ge 0, \quad \sum_{j=0}^{n-1} p_j = 1 $$...
TAOCP 3.4.1 Exercise 13
Section 3.4.1: Numerical Distributions Exercise 13. [ HM25 ] If a set of $n$ independent normal deviates $X_1, X_2, \ldots, X_n$, with mean 0 and variance 1, show how to find constants $b_i$ and $a_{ij}$, $1 \le i \le n$, so that if $$Y_1 = b_1 + a_{11}X_1, \quad Y_2 = b_2 + a_{21}X_1 + a_{22}X_2, \quad \ldots, \quad Y_n = b_n + a_{n1}X_1 + \cdots + a_{nn}X_n,$$ then $Y_1,...
TAOCP 3.4.1 Exercise 6
Section 3.4.1: Numerical Distributions Exercise 6. [ HM21 ] A quantity $X$ is computed by the following method: Step 1. Generate two independent uniform deviates $U$ and $V$. Step 2. If $U^2 + V^2 \ge 1$, return to step 1; otherwise set $X \leftarrow U$. What is the distribution function of $X$? How many times will step 1 be performed? (Give the mean and standard deviation.) Verified: yes Solve time:...
TAOCP 3.3.4 Exercise 29
Section 3.3.4: The Spectral Test Exercise 29. [ HM22 ] Prove that the quantity $r_{\max}$ is never larger than $1/(\sqrt{8},\nu_t)$. Verified: no Solve time: 4m58s Solution We are asked to prove that $$ r_{\max} \le \frac{1}{\sqrt{8}, \nu_t}, $$ where $r_{\max}$ is the maximal value of $$ r(u_1,\ldots,u_t) = \prod_{j=1}^t r(u_j), \qquad r(u) = \begin{cases} 1,& u=0,\[1mm] \dfrac{1}{2|u|},& u \neq 0, \end{cases} $$ over all nonzero integer vectors $(u_1,\ldots,u_t)$ satisfying the...
TAOCP 3.3.4 Exercise 25
Section 3.3.4: The Spectral Test Exercise 25. [ HM24 ] Let $d$ be a divisor of $m$ and let $0 \le q < d$. Prove that $\sum r(k)$, summed over all $0 \le k < m$ such that $k \bmod d = q$, is at most $(2/d\pi)\ln(m/d) + O(1)$. (Here $r(k)$ is defined in Eq. (40) when $t = 1$.) Verified: yes Solve time: 5m55s Solution Let $r(k)$ be defined...
TAOCP 1.3.3 Exercise 19
Section 1.3.3: Applications to Permutations Exercise 19. [ HM21 ] Show that, in the notation of Eq. (25), the number $P_{n0}$ of derangements is exactly equal to $n!/e$ rounded to the nearest integer, for all $n \ge 1$. Verified: yes Solve time: 47s Solution Equation (25) gives the number of derangements as $$ P_{n0} = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}. $$ Let $$ S_n=\sum_{k=0}^{n}\frac{(-1)^k}{k!}. $$ Since $$ e^{-1} = \sum_{k=0}^{\infty}\frac{(-1)^k}{k!}, $$ we have $$...
TAOCP 1.3.2 Exercise 6
Section 1.3.2: The MIX Assembly Language Exercise 6. [ HM20 ] (a) Show that if n is not prime, n has a divisor d with 1 < d \le \sqrt{n} . (b) Use this fact to show that the test in step P7 of Algorithm P proves that N is prime. Verified: yes Solve time: 1m30s Solution (a) Let $n$ be a composite integer, $n > 1$. Then there exist...
TAOCP 1.2.8 Exercise 24
Section 1.2.8: Fibonacci Numbers Exercise 24. [ HM20 ] Evaluate the $n \times n$ determinant $$ \begin{pmatrix} 1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \ 1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \ 0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \ \vdots & \vdots & \vdots...
TAOCP 1.2.9 Exercise 3
Section 1.2.9: Generating Functions Exercise 3. [ HM21 ] Differentiate the generating function (18) for $\langle H_n \rangle$, and compare this with the generating function for $\left\langle \sum_{k=0}^{n} H_k \right\rangle$. What relation can you deduce? Verified: yes Solve time: 5m40s Solution Equation (18) gives the generating function for the harmonic numbers: $$ G(z)=\sum_{n\ge0}H_nz^n =\frac{1}{1-z}\ln\frac1{1-z}. $$ Differentiating and using the product rule, $$ G'(z) =\frac{1}{(1-z)^2}\ln\frac1{1-z} +\frac{1}{(1-z)^2. } $$ Hence $$ zG'(z)...
TAOCP 1.2.9 Exercise 13
Section 1.2.9: Generating Functions Exercise 13. [ HM22 ] The Laplace transform of a function $f(x)$ is the function $$ Lf(s) = \int_0^\infty e^{-st}f(t),dt. $$ Given that $a_0,a_1,a_2,\ldots$ is an infinite sequence having a convergent generating function, let $f(x)$ be the step function $\sum_k a_k [0 \le k \le x]$. Express the Laplace transform of $f(x)$ in terms of the generating function $G$ for this sequence. Verified: yes Solve time:...
TAOCP 1.2.9 Exercise 14
Section 1.2.9: Generating Functions Exercise 14. [ HM21 ] Prove Eq. (13). Verified: yes Solve time: 52s Solution Let $$ G(z)=\sum_{n\ge 0} a_n z^n. $$ Consider the right-hand side of Eq. (13): $$ \frac{1}{m}\sum_{0\le k<m}\omega^{-kr}G(\omega^k z). $$ Substituting the definition of $G$ gives $$ \frac{1}{m}\sum_{0\le k<m}\omega^{-kr}\sum_{n\ge 0} a_n(\omega^k z)^n. $$ Reordering the summations yields $$ \sum_{n\ge 0} a_n z^n \cdot \frac{1}{m}\sum_{0\le k<m}\omega^{kn}\omega^{-kr} = \sum_{n\ge 0} a_n z^n \cdot \frac{1}{m}\sum_{0\le k<m}\omega^{k(n-r)}....
TAOCP 1.2.8 Exercise 33
Section 1.2.8: Fibonacci Numbers Exercise 33. [ HM24 ] Given that $z=\pi/2 + i\ln\phi$, show that $\sin nz/\sin z = i^{,1-n}F_n$. Verified: no Solve time: - Solution By the addition formulas for the sine function, $$ \sin\left(\frac{\pi}{2}+w\right)=\cos w. $$ Hence, with $$ z=\frac{\pi}{2}+i\ln\phi, $$ we have $$ \sin z=\cos(i\ln\phi). $$ Since $$ \cos(ix)=\frac{e^{-x}+e^x}{2}, $$ it follows that $$ \sin z =\frac{\phi+\phi^{-1}}{2}. $$ Now $\phi^2=\phi+1$, therefore $$ \phi+\phi^{-1} =\phi+\phi-1 =2\phi-1 =\sqrt5,...
TAOCP 1.2.7 Exercise 20
Section 1.2.7: Harmonic Numbers Exercise 20. [ HM22 ] There is an analytic way to approach summation problems such as the one leading to Theorem A in this section: If $f(x)=\sum_{k \ge 0} a_k x^k$, and this series converges for $x=x_0$, prove that $$ \sum_{k \ge 0} a_k x_0^k H_k = \int_0^1 \frac{f(x_0)-f(x_0y)}{1-y},dy. $$ Verified: no Solve time: 4m12s Solution Let $$ b_k=a_kx_0^k, \qquad f(x_0)=\sum_{k\ge0}b_k, $$ and let $$ B_n=\sum_{k=0}^n...
TAOCP 1.2.7 Exercise 23
Section 1.2.7: Harmonic Numbers Exercise 23. [ HM20 ] By considering the function $\Gamma'(x)/\Gamma(x)$, generalize $H_n$ to noninteger values of $n$. You may use the fact that $\Gamma'(1)=-\gamma$, anticipating the next exercise. Verified: no Solve time: - Solution For positive integers $n$, $$ H_n=\sum_{k=1}^n \frac1k. $$ The exercise asks for a continuation of this function to noninteger values by means of the logarithmic derivative of the gamma function, $$ \psi(x)=\frac{\Gamma'(x)}{\Gamma(x)}....
TAOCP 1.2.7 Exercise 8
Section 1.2.7: Harmonic Numbers Exercise 8. [ HM18 ] Compare Eq. (8) with $\sum_{k=1}^{n}\ln k$; estimate the difference as a function of $n$. Verified: yes Solve time: 1m23s Solution Equation (8) gives $$ \sum_{k=1}^{n}H_k=(n+1)H_n-n. $$ The analogous quantity for logarithms is $$ \sum_{k=1}^{n}\ln k=\ln(n!). $$ Since $$ H_n=\sum_{k=1}^{n}\frac1k, $$ the standard comparison between the harmonic series and the logarithm yields $$ H_n=\ln n+\gamma+\delta_n, $$ where $\gamma$ is Euler's constant and...
TAOCP 1.2.7 Exercise 24
Section 1.2.7: Harmonic Numbers Exercise 24. [ HM21 ] Show that $$ xe^{\gamma x} \prod_{k \ge 1} \left(\left(1+\frac{x}{k}\right)e^{-x/k}\right) = \frac{1}{\Gamma(x)}. $$ (Consider the partial products of this infinite product.) Verified: yes Solve time: 2m38s Solution Let $$ P_n(x)=x e^{\gamma x}\prod_{k=1}^{n}\left(1+\frac{x}{k}\right)e^{-x/k}. $$ We shall show that $$ \lim_{n\to\infty}P_n(x)=\frac1{\Gamma(x)}. $$ The hint suggests working directly with the partial products. Using $\Gamma(y+1)=y\Gamma(y)$, we have $$ \Gamma(n+1+x) =\Gamma(x+1)\prod_{k=1}^{n}(x+k), $$ and $$ \Gamma(n+1)=\prod_{k=1}^{n}k. $$ Therefore...
TAOCP 1.2.6 Exercise 41
Section 1.2.6: Binomial Coefficients Exercise 41. [ HM22 ] Prove that $$ B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}. $$ Verified: no Solve time: - Solution Define $$ I(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}. $$ We will show that $I(x,y)$ satisfies the same defining relations as $B(x,y)$ in Exercise 40. From the definition of the gamma function, $$ \Gamma(x+1)=x\Gamma(x), \qquad x>0. $$ Hence $$ I(x,1) = \frac{\Gamma(x)\Gamma(1)}{\Gamma(x+1)}. $$ Since $$ \Gamma(1)=\int_0^\infty e^{-t},dt=1, $$ and since $\Gamma(x+1)=x\Gamma(x)$, $$ I(x,1) = \frac{\Gamma(x)}{x\Gamma(x)} =...
TAOCP 1.2.6 Exercise 40
Section 1.2.6: Binomial Coefficients Exercise 40. [ HM17 ] The beta function $B(x,y)$ is defined for positive real numbers $x,y$ by $$ B(x,y) = \int_0^1 t^{x-1}(1-t)^{y-1},dt. $$ Show that: $B(x,1)=B(1,x)=1/x$. $B(x+1,y)+B(x,y+1)=B(x,y)$. $B(x,y)=((x+y)/y)B(x,y+1)$. Verified: no Solve time: - Solution By definition, $$ B(x,1) = \int_0^1 t^{x-1} (1-t)^{1-1}, dt = \int_0^1 t^{x-1}, dt. $$ Since $x>0$, the integral converges and evaluates to $$ \int_0^1 t^{x-1}, dt = \left[ \frac{t^x}{x} \right]_0^1 = \frac{1}{x}....
TAOCP 1.2.6 Exercise 44
Section 1.2.6: Binomial Coefficients Exercise 44. [ HM20 ] Using the generalized binomial coefficient suggested in exercise 42, show that $$ \binom{r}{1/2} = \frac{2^{2r+1}}{\binom{2r}{r}\pi}. $$ Verified: no Solve time: - Solution Exercise 42 suggests extending the binomial coefficient to arbitrary arguments by means of the beta function. Since exercise 41 established $$ B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}, $$ and equation (3) gives $$ \binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!}, $$ the corresponding gamma-function form is $$ \binom{r}{k}...
TAOCP 1.2.6 Exercise 26
Section 1.2.6: Binomial Coefficients Exercise 26. [ HM25 ] Using the assumptions of the previous exercise, prove that $$ \sum_k \binom{r-tk}{k} z^k = \frac{x^{r+1}}{(t+1)x-t}. $$ Verified: no Solve time: - Solution Exercise 25 established that, under the assumptions of Example 4, $$ \sum_k A_k(r,t) z^k = x^r, \qquad z=x^{t+1}-x^t, $$ provided that $x$ is sufficiently close to $1$. By the definition of $A_k(r,t)$ in Example 4, $$ A_k(r,t)=\frac{r-tk}{r}\binom{r}{k}. $$ Using...
TAOCP 1.2.6 Exercise 43
Section 1.2.6: Binomial Coefficients Exercise 43. [ HM20 ] Show that $B(1/2,1/2)=\pi$. Verified: no Solve time: - Solution We are asked to evaluate the beta function $$ B!\left(\frac{1}{2},\frac{1}{2}\right) = \int_0^1 t^{-1/2} (1-t)^{-1/2}, dt. $$ We perform the substitution $t = \sin^2\theta$, so that $dt = 2\sin\theta\cos\theta, d\theta$. Then $$ t^{-1/2} = (\sin^2\theta)^{-1/2} = \frac{1}{\sin\theta}, \qquad (1-t)^{-1/2} = (\cos^2\theta)^{-1/2} = \frac{1}{\cos\theta}. $$ Hence the integrand transforms as $$ t^{-1/2} (1-t)^{-1/2} ,...
TAOCP 1.2.6 Exercise 45
Section 1.2.6: Binomial Coefficients Exercise 45. [ HM21 ] Using the generalized binomial coefficient suggested in exercise 42, find $$ \lim_{r \to \infty}\frac{\binom{r}{k}}{r^k}. $$ Verified: no Solve time: - Solution By equation (3), $$ \binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!}, \qquad \text{integer } k \ge 0. $$ Hence $$ \frac{\binom{r}{k}}{r^k} = \frac{r(r-1)\cdots(r-k+1)}{k!,r^k} = \frac1{k!} \prod_{j=0}^{k-1}\left(1-\frac{j}{r}\right). $$ Here $k$ is fixed. For each $j$ with $0\le j\le k-1$, $$ \lim_{r\to\infty}\left(1-\frac{j}{r}\right)=1. $$ Since the product...
TAOCP 1.2.6 Exercise 27
Section 1.2.6: Binomial Coefficients Exercise 27. [ HM21 ] Solve Example 4 in the text by using the result of exercise 25; and prove Eq. (26) from the preceding two exercises. Verified: no Solve time: - Solution We begin with the setup from Exercise 25. Let $A_n(x,t)$ be defined as in Example 4, and let $z = x^{t+1} - x^t$. Exercise 25 established that, for $x$ sufficiently close to 1,...
TAOCP 1.2.3 Exercise 35
Section 1.2.3: Sums and Products Exercise 35. [ HM20 ] The notation $\sup_{R(j)} a_j$ is used to denote the least upper bound of the elements $a_j$, in a manner exactly analogous to the $\sum$- and $\prod$-notations. (When $R(j)$ is satisfied for only finitely many $j$, the notation $\max_{R(j)} a_j$ is often used to denote the same quantity.) Show how rules (a), (b), (c), and (d) can be adapted for manipulation...
TAOCP 1.2.2 Exercise 29
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 29. [ HM20 ] Let $x$ be a real number greater than 1. (a) For what real number $b > 1$ is $b \log_b x$ a minimum? (b) For what integer $b > 1$ is it a minimum? (c) For what integer $b > 1$ is $(b + 1) \log_b x$ a minimum? Verified: yes Solve time: 35s Solution Let $x > 1$...
TAOCP 1.2.3 Exercise 5
Section 1.2.3: Sums and Products Exercise 5. ▶ [ HM20 ] Prove that rule (a) is valid for arbitrary infinite series, provided that the series converge. Verified: yes Solve time: 2m22s Solution Let $$ \sum_{R(i)} a_i = A, \qquad \sum_{S(j)} b_j = B $$ be convergent infinite series. Let $$ A_m=\sum_{\substack{i\in R\ i\le m}} a_i, \qquad B_n=\sum_{\substack{j\in S\ j\le n}} b_j . $$ Then $$ A_m\to A, \qquad B_n\to B....
TAOCP 1.2.3 Exercise 8
Section 1.2.3: Sums and Products Exercise 8. [ HM25 ] Find an example of infinite series in which Eq. (7) is false. Verified: yes Solve time: 35s Solution Equation (7) asserts that $$ \sum_{R(i)} \sum_{S(j)} a_{ij} = \sum_{S(j)} \sum_{R(i)} a_{ij}. $$ The text states that this operation is not always valid for infinite series. We construct a counterexample. Define $$ a_{ij} = \begin{cases} 1, & \text{if } j=i,\ -1, &...
TAOCP 1.2.3 Exercise 6
Section 1.2.3: Sums and Products Exercise 6. [ HM20 ] Prove that rule (d) is valid for an arbitrary infinite series, provided that any three of the four sums exist. Verified: yes Solve time: 2m06s Solution Let $$ A=\sum_{R(j)} a_j,\qquad B=\sum_{S(j)} a_j,\qquad C=\sum_{R(j)\text{ or }S(j)} a_j,\qquad D=\sum_{R(j)\text{ and }S(j)} a_j . $$ We must prove that $$ A+B=C+D, $$ provided that any three of the four sums exist. Using Iverson's...
TAOCP 1.2.3 Exercise 7
Section 1.2.3: Sums and Products Exercise 7. [ HM23 ] Given that $c$ is an integer, show that $\sum_{R(j)} a_j = \sum_{R(c-j)} a_{c-j}$, even if both series are infinite. Verified: yes Solve time: 37s Solution Let $S=\sum_{R(j)} a_j.$ Define the change of variable $i=c-j.$ Since $c$ is an integer, the mapping $j \mapsto c-j$ is a permutation of the integers. Indeed, for every integer $i$ there exists exactly one integer...
TAOCP 1.2.11.3 Exercise 1
Section 1.2.11.3: Some Asymptotic Calculations Exercise 1. [ HM20 ] Prove Eq. (5) by induction on $n$. Verified: yes Solve time: 1m21s Solution Equation (5) states that $$ f(x) = \sum_{k=0}^{n}\frac{f^{(k)}(0)}{k!}x^k + \frac1{n!}\int_0^x f^{(n+1)}(t)(x-t)^n,dt. \tag{5} $$ We prove this formula by induction on $n$. For $n=0$, $$ f(x) = f(0)+\int_0^x f'(t),dt, $$ by the fundamental theorem of calculus. This is exactly (5) when $n=0$. Assume that (5) holds for some...
TAOCP 1.2.10 Exercise 22
Section 1.2.10: Analysis of an Algorithm Exercise 22. [ HM22 ] Suppose $X$ has the generating function $(q_1+p_1z)(q_2+p_2z)\cdots(q_n+p_nz)$, where $p_k+q_k=1$ for $1 \le k \le n$. Let $\mu=EX=p_1+\cdots+p_n$. a) Prove that $$ \Pr(X \le \mu r) \le (r^{-r}e^{r-1})^\mu, \qquad 0<r\le 1; $$ $$ \Pr(X \ge \mu r) \le (r^{-r}e^{r-1})^\mu, \qquad r\ge 1. $$ Verified: yes Solve time: 1m09s Solution Let $X$ be a sum of independent Bernoulli random variables $X_1,X_2,\ldots,X_n$,...
TAOCP 1.2.11.3 Exercise 5
Section 1.2.11.3: Some Asymptotic Calculations Exercise 5. [ HM24 ] Show that $R$ in Eq. (21) is $O(n^n e^{-n})$. Verified: yes Solve time: 3m57s Solution We are asked to show that the remainder term $R$ in Eq. (21) satisfies $$ R = O(n^n e^{-n}). $$ Equation (21) in TAOCP, Section 1.2.11.3, expresses a sum in terms of an integral plus Euler-Maclaurin corrections: $$ \sum_{k=0}^{n} k^{,n+1/2} e^{-k} = \int_0^n f(x),dx +...
TAOCP 1.2.11.3 Exercise 6
Section 1.2.11.3: Some Asymptotic Calculations Exercise 6. [ HM20 ] Prove Eq. (23). Verified: no Solve time: 1m55s Solution Write $$ \frac{(n+\alpha)^n}{n^{,n+\beta}} = n^{\alpha-\beta}\left(1+\frac{\alpha}{n}\right)^n. $$ Take logarithms of the second factor: $$ \ln\left(1+\frac{\alpha}{n}\right) = \frac{\alpha}{n} - \frac{\alpha^2}{2n^2} + O(n^{-3}). $$ Multiplying by $n$ gives $$ n\ln\left(1+\frac{\alpha}{n}\right) = \alpha - \frac{\alpha^2}{2n} + O(n^{-2}). $$ Exponentiation yields $$ \left(1+\frac{\alpha}{n}\right)^n = \exp\left(\alpha - \frac{\alpha^2}{2n} + O(n^{-2})\right) = e^\alpha \exp\left(-\frac{\alpha^2}{2n} + O(n^{-2})\right). $$ Expanding...
TAOCP 1.2.11.2 Exercise 2
Section 1.2.11.2: Euler's Summation Formula Exercise 2. [ HM20 ] Explain why the sequence defined by Eq. (4), not merely any sequence satisfying Eq. (9), is necessary for the validity of Eq. (10). Verified: yes Solve time: 2m23s Solution In Section 1.2.11.2, Eq. (10) gives Euler's summation formula in the form $$ \sum_{k=m}^{n-1} f(k) = \int_m^n f(x),dx - \sum_{r=1}^{p} \frac{B_r}{r!} \left(f^{(r-1)}(n) - f^{(r-1)}(m)\right) + R_p, $$ where $B_r$ are the...
TAOCP 1.2.11.2 Exercise 4
Section 1.2.11.2: Euler's Summation Formula Exercise 4. [ HM20 ] ( Sums of powers. ) When $f(x)=x^m$, the high-order derivatives of $f$ are all zero, so Euler's summation formula gives an exact value for the sum $$ S_m(n) = \sum_{0 \le k < n} k^m. $$ Express $S_m(n)$ in terms of Bernoulli polynomials. Verified: yes Solve time: 43s Solution Let $f(x) = x^m$, where $m$ is a nonnegative integer. Then...
TAOCP 1.2.11.3 Exercise 2
Section 1.2.11.3: Some Asymptotic Calculations Exercise 2. [ HM20 ] Obtain Eq. (7) from Eq. (6). Verified: yes Solve time: 58s Solution We are asked to derive the series expansion $$ \gamma(a,x) = \sum_{k\ge 0} \frac{(-1)^k x^{k+a}}{k!(k+a)} \tag{7} $$ starting from the definition of the incomplete gamma function $$ \gamma(a,x) = \int_0^x e^{-t} t^{a-1}, dt, \qquad a>0. \tag{6} $$ We begin by expanding the exponential function in its Maclaurin series:...
TAOCP 1.2.11.2 Exercise 3
Section 1.2.11.2: Euler's Summation Formula Exercise 3. [ HM20 ] Let $C_{mn}=(B_m/m!)(f^{(m-1)}(n)-f^{(m-1)}(1))$ be the $m$th correction term in Euler's summation formula. Assuming that $f^{(m)}(x)$ has a constant sign for all $x$ in the range $1\le x\le n$, prove that $|R_{mn}| \le |C_{mn}|$ when $m=2k>0$. Verified: yes Solve time: 1m50s Let $m=2k>0$. Write $$ S(x)=f^{(m-1)}(x), \qquad S'(x)=f^{(m)}(x), $$ so $S'$ has constant sign on $[1,n]$, hence $S$ is monotone. We use...
TAOCP 1.2.11.2 Exercise 12
Section 1.2.11.2: Euler's Summation Formula Exercise 12. [ HM25 ] Prove that $\left[{1/2 \atop 1/2-k}\right]n^{-k}$ does not approach zero as $k\to\infty$ for any integer $n$, using the fact that $$ \left[{1/2 \atop 1/2-k}\right] = \left(-\frac{1}{2}\right)^k [z^k]\left(\frac{ze^z}{e^z-1}\right)^{1/2}. $$ Verified: no Solve time: 3m10s The critical issue is not the manipulation of generating functions but the implicit assumption that the coefficient sequence is governed by a finite radius of convergence. That assumption...
TAOCP 1.2.10 Exercise 12
Section 1.2.10: Analysis of an Algorithm Exercise 12. [ HM21 ] When $G(z)=p_0+p_1z+p_2z^2+\cdots$ represents a probability distribution, the quantities $$ M_n = \sum_k k^n p_k \qquad\text{and}\qquad m_n = \sum_k (k-M_1)^n p_k $$ are called the "$n$th moment" and "$n$th central moment," respectively. Show that $$ G(e^t) = 1 + M_1t + M_2t^2/2! + \cdots; $$ then use Arbogast's formula (exercise 1.2.5-21) to show that $$ \kappa_n = \sum_{k_1,k_2,\ldots,k_n \ge 0}...
TAOCP 1.2.11.3 Exercise 15
Section 1.2.11.3: Some Asymptotic Calculations Exercise 15. [ HM20 ] Show that the following integral is related to $Q(n)$: $$ \int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z},dz. $$ Verified: no Solve time: 2m08s Let $$ I_n=\int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z},dz . $$ We first evaluate $I_n$ exactly. Using the binomial theorem, $$ \left(1+\frac{z}{n}\right)^n =\sum_{k=0}^{n}\binom{n}{k}\left(\frac{z}{n}\right)^k, $$ hence $$ I_n =\sum_{k=0}^{n}\binom{n}{k}\frac1{n^k} \int_0^\infty z^k e^{-z},dz . $$ Since $$ \int_0^\infty z^k e^{-z},dz=\Gamma(k+1)=k!, $$ we obtain $$ I_n =\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{n^k}. $$...
TAOCP 1.2.10 Exercise 15
Section 1.2.10: Analysis of an Algorithm Exercise 15. [ HM23 ] When the probability that some quantity has the value $k$ is $e^{-\mu}(\mu^k/k!)$, it is said to have the Poisson distribution with mean $\mu$. a) What is the generating function for this set of probabilities? b) What are the values of the semi-invariants? c) Show that as $n\to\infty$ the Poisson distribution with mean $np$ approaches the normal distribution in the...
TAOCP 1.2.11.2 Exercise 10
Section 1.2.11.2: Euler's Summation Formula Exercise 10. [ HM22 ] Make a statement similar to that in exercise 9 about $\ln(1+O(z^m))$. Verified: yes Solve time: 45s Solution Let $u(z)=O(z^m)$ as $z\to 0$, with $m>0$. Then there exist positive constants $L$ and $z_0$ such that $|u(z)| \le L|z|^m$ for all $|z|\le z_0$, and hence $u(z)\to 0$ as $z\to 0$. For $|u|<1$, the expansion $$ \ln(1+u)=u+O(u^2) $$ holds, since $\ln(1+u)$ has a...
TAOCP 1.2.10 Exercise 2
Section 1.2.10: Analysis of an Algorithm Exercise 2. [ HM16 ] Derive Eq. (13) from Eq. (10). Verified: yes Solve time: 47s Solution We are asked to derive Eq. (13) from Eq. (10). Begin by recalling the definitions in Eq. (10). Let $$ G(z) = p_0 + p_1 z + p_2 z^2 + \cdots $$ be a generating function with $p_k$ the probability that an event takes value $k$. Then...
TAOCP 1.2.10 Exercise 21
Section 1.2.10: Analysis of an Algorithm Exercise 21. [ HM21 ] Let $X$ be the number of heads that occur when a random coin is flipped $n$ times, with generating function (18). Use (25) to prove that $$ \Pr(X \ge n(p+\epsilon)) \le e^{-\epsilon^2 n/(2q)} $$ when $\epsilon \ge 0$, and obtain a similar estimate for $\Pr(X \le n(p-\epsilon))$. Verified: yes Solve time: 2m25s Let $X\sim \mathrm{Bin}(n,p)$, $q=1-p$, and let $0\le...