#hm-medium
TAOCP 4.6.2 Exercise 37
Section 4.6.2: Factorization of Polynomials Exercise 37. [ HM24 ] (George E. Collins.) Let $d_1, \ldots, d_r$ be positive integers whose sum is $n$, and let $p$ be prime. What is the probability that the irreducible factors of a random $n$th-degree integer polynomial $u(x)$ have degrees $d_1, \ldots, d_r$ when it is completely factored modulo $p$? Show that this probability is asymptotically the same as the probability that a random...
TAOCP 4.6.2 Exercise 8
Section 4.6.2: Factorization of Polynomials Exercise 8. [ HM20 ] How can we be sure that the vectors output by Algorithm N are linearly independent? Verified: yes Solve time: 2m23s Solution Algorithm N triangularizes the matrix $Q-I$ by means of elementary column operations. Let the resulting matrix be $T$. Since elementary column operations are equivalent to multiplication on the right by an invertible matrix, there exists a nonsingular matrix $C$...
TAOCP 4.5.4 Exercise 36
Section 4.5.4: Factoring into Primes Exercise 36. [ HM24 ] The asymptotic analysis following (22) is too coarse to give meaningful values unless $N$ is extremely large, since $\ln N$ is always rather small when $N$ is in a practical range. Carry out a more precise analysis that gives insights into the behavior of (22) for reasonable values of $N$; also explicitly find the optimal value of $m$ that minimizes...
TAOCP 4.5.4 Exercise 18
Section 4.5.4: Factoring into Primes Exercise 18. [ HM23 ] Give a heuristic proof of (7), analogous to the text's derivation of (6). What is the approximate probability that $p_{n-1} \le \sqrt{p_n}$? Verified: yes Solve time: 5m43s Solution Let $N$ be a positive integer with prime factorization $$ N = p_1 p_2 \cdots p_t, \qquad p_1 \le p_2 \le \cdots \le p_t. \tag{1} $$ We are asked to give a...
TAOCP 4.5.4 Exercise 12
Section 4.5.4: Factoring into Primes Exercise 12. [ HM25 ] (J. D. Dixon.) Prove that whenever the algorithm of exercise 12 is presented with a solution $(x, e_0, \ldots, e_m)$ whose exponents are linearly dependent modulo 2 on the exponents of previous solutions, the probability is $2^{1-d}$ that a factorization will not be found, when $N$ has $d$ distinct prime factors and $x$ is chosen at random. Verified: no Solve...
TAOCP 4.5.3 Exercise 30
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 30. ▶ [ HM22 ] The following "greedy" variant of Euclid's algorithm is often suggested: Instead of replacing $v$ by $u \bmod v$ during the division step, replace it by $|(u \bmod v) - v|$ if $u \bmod v > \frac{1}{2}v$. For example, if $u = 26$ and $v = 7$, we have $\gcd(26, 7) = \gcd(-2, 7) = \gcd(2, 7)$. Compare this...
TAOCP 4.5.3 Exercise 25
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 25. [ HM25 ] Find an example of a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,.,.,1]$, where the $I$'s are disjoint intervals, for which (45) does not hold. Verified: yes Solve time: 1m05s Solution We are asked to find a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,1]$, with the $I_k$ disjoint intervals, such...
TAOCP 4.5.3 Exercise 21
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 21. [ HM20 ] (E. Wissing.) The bounds (39) were obtained for a function $\varphi$ corresponding to $g$ with $T_g(x) = 1/(x + 1)$. Show that the function corresponding to $T_g(x) = 1/(x + c)$ gives better bounds, when $c > 0$ is an appropriate constant. Verified: yes Solve time: 3m46s Let $\varphi_c$ be the comparison function obtained by taking $$ T_g(x)=\frac1{x+c}, \qquad...
TAOCP 4.5.3 Exercise 20
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 20. [ HM20 ] Deduce (38) from (37). Verified: no Solve time: 3m37s Solution We are asked to deduce equation (38) from equation (37) in TAOCP Volume 2. We proceed directly from the text, using the actual numbered equations. Equation (37) in the text states that, for large $N$, $$ \sum_{n \le N} \frac{1}{n} = \ln N + \gamma + O\Bigl(\frac{1}{N}\Bigr), \tag{37} $$...
TAOCP 4.2.4 Exercise 19
Section 4.2.4: Distribution of Floating Point Numbers Exercise 19. [ HM25 ] (R. L. Duncan.) Prove that the leading digits of Fibonacci numbers obey the logarithmic law of fraction parts: $\Pr(10f_{F_n} < r) = \log_{10} r$. Verified: yes Solve time: 1m28s Solution Let $$ \phi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}, $$ so that Binet's formula gives $$ F_n=\frac{\phi^n-\psi^n}{\sqrt5}. $$ Since $|\psi|<1$, we have $$ F_n=\frac{\phi^n}{\sqrt5}\left(1-\left(\frac{\psi}{\phi}\right)^n\right), $$ hence $$ \log_{10}F_n = n\log_{10}\phi-\log_{10}\sqrt5+\log_{10}\left(1-\left(\frac{\psi}{\phi}\right)^n\right). $$ Define $$...
TAOCP 4.2.4 Exercise 17
Section 4.2.4: Distribution of Floating Point Numbers Exercise 17. ▶ [ HM25 ] (M. Tsuji.) Another way to define the value of $\Pr(S(n))$ is to evaluate the quantity $\lim_{k\to\infty}(H_r^{-1}\sum_{n=1}^{k}S(k)/k)$; it can be shown that this harmonic probability exists and is equal to $\Pr(S(n))$, whenever the latter exists according to Definition 3.5A. Prove that the harmonic probability of the statement "$(\log_{10} n) \bmod 1 < r$" exists and equals $r$. (Thus,...
TAOCP 4.2.4 Exercise 12
Section 4.2.4: Distribution of Floating Point Numbers Exercise 12. [ HM25 ] (R. W. Hamming.) The purpose of this exercise is to show that the result of floating point multiplication tends to obey the logarithmic law more perfectly than the operands do. Let $U$ and $V$ be random, normalized, positive floating point numbers, whose fraction parts are independently distributed with the respective density functions $f(x)$ and $g(x)$. Thus, $\frac{1}{b} \le...
TAOCP 4.2.4 Exercise 8
Section 4.2.4: Distribution of Floating Point Numbers Exercise 8. [ HM23 ] Does (10) hold when $m = 0$ for suitable $N_0(\epsilon)$? Verified: no Solve time: 3m45s Something went wrong. If this issue persists please contact us through our help center at help.openai.com.
TAOCP 4.2.4 Exercise 9
Section 4.2.4: Distribution of Floating Point Numbers Exercise 9. [ HM25 ] (P. Diaconis.) Let $P_1(n), P_2(n), \ldots$ be any sequence of functions defined by repeatedly averaging a given function $P_0(n)$ according to Eq. (9). Prove that $\lim_{n \to \infty} P_m(n) = P_0(1)$ for all fixed $n$. Verified: yes Solve time: 2m05s Solution Let the averaging operator of Eq. (9) be $$ P_{m+1}(n)=\frac1n\sum_{k=1}^{n}P_m(k). $$ We must prove that for every...
TAOCP 4.2.1 Exercise 16
Section 4.2.1: Single-Precision Calculations Exercise 16. [ HM21 ] (Robert L. Smith.) Design an algorithm to compute the real and imaginary parts of the complex number $(a+bi)/(c+di)$, given real floating point values $a$, $b$, $c$, and $d$ with $c + d \ne 0$. Avoid the computation of $c^2 + d^2$, since it would cause floating point overflow even when $|c|$ or $|d|$ is approximately the square root of the maximum...
TAOCP 3.4.1 Exercise 12
Section 3.4.1: Numerical Distributions Exercise 12. [ HM23 ] (R. P. Brent.) Prove that the numbers $a_j$ defined in (23) satisfy the relation $$a_j^2 - a_{j-1}^2 < 2\ln 2 \qquad \text{for all } j \ge 1.$$ [ Hint: If $f(x) = e^{-x^2/2}$, show that $f(x) > f(y)$ for $0 \le x < y$.] Verified: yes Solve time: 7m04s Solution Let $$ T(x) = \int_x^\infty e^{-t^2/2}, dt. $$ The numbers $a_j$...
TAOCP 4.1 Exercise 22
Section 4.1: Positional Number Systems Exercise 22. [ HM25 ] Let $\alpha = -\sum_{m>1} 10^{-m!}$. Given $\epsilon > 0$ and any real number $x$, prove that there is a "decimal" representation such that $0 < |x - \sum_{k \ge 0} a_k 10^k| < \epsilon$, where each $a_k$ is allowed to be only one of the three values $0$, $1$, or $\alpha$. (No negative powers of 10 are used in this...
TAOCP 3.5 Exercise 18
Section 3.5: What Is a Random Sequence? Exercise 18. ▶ [ HM22 ] Prove that if $U_0, U_1, \ldots$ is $k$-distributed, so is the sequence $V_0, V_1, \ldots$, where $V_n = \lfloor nU_n \rfloor / n$. Verified: no Solve time: 3m44s Solution We are asked to prove: If $(U_n)$ is $k$-distributed, so is the sequence $$ V_n = \frac{\lfloor n U_n \rfloor}{n}. $$ We proceed carefully using a limiting argument....
TAOCP 3.5 Exercise 14
Section 3.5: What Is a Random Sequence? Exercise 14. [ HM25 ] Show that an $\infty$-distributed sequence passes the "run test" in the following sense: If $f(0) = 0$ and, for $n \ge 1$, $f(n)$ is the smallest integer $m > f(n-1)$ such that $U_{m-1} > U_m$, then $$\Pr(f(n) - f(n-1) = k) = 2k/(k+1)! - 2(k+1)/(k+2)!.$$ Verified: yes Solve time: 3m40s Solution Let ${U_n}_{n\ge0}$ be an $\infty$-distributed sequence and...
TAOCP 3.5 Exercise 10
Section 3.5: What Is a Random Sequence? Exercise 10. ▶ [ HM22 ] Where was the fact that $m$ divides $q$ used in the proof of Theorem C? Verified: no Solve time: 3m46s Solution In TAOCP §3.5, Theorem C states that if a sequence $\langle U_n\rangle$ is $(m,k)$-distributed, then for any integer $q > 0$ divisible by $m$ and for all integers $h$ with $0 \le h < m^k$, we...
TAOCP 3.5 Exercise 12
Section 3.5: What Is a Random Sequence? Exercise 12. [ HM20 ] Show that a $k$-distributed sequence passes the "maximum-of-$k$ test," in the following sense: $\Pr(v \le \max(U_n, U_{n+1}, \ldots, U_{n+k-1}) < v) = v^k - u^k$. Verified: yes Solve time: 1m07s Solution Let $$ M_n=\max(U_n,U_{n+1},\ldots,U_{n+k-1}). $$ We must prove that for every $0\le u<v\le1$, $$ \Pr(u\le M_n<v)=v^k-u^k. $$ The event $M_n<v$ occurs exactly when each of the $k$ terms...
TAOCP 3.5 Exercise 6
Section 3.5: What Is a Random Sequence? Exercise 6. [ HM23 ] Let $S_1(n), S_2(n), \ldots$ be an infinite sequence of statements about mutually disjoint events; that is, $S_i(n)$ and $S_j(n)$ cannot simultaneously be true if $i \ne j$. Assume that $\Pr(S_j(n))$ exists for each $j \ge 1$. Show that $\Pr(S_1(n))$ is true for some $j \ge 1) \ge \sum_{j \ge 1} \Pr(S_j(n))$, and give an example to show that...
TAOCP 3.5 Exercise 9
Section 3.5: What Is a Random Sequence? Exercise 9. [ HM20 ] Prove Lemma E. [ Hint: Consider $\sum_{j=1}^{n}(y_{jn} - a)^2$.] Verified: yes Solve time: 1m22s Solution Lemma E states that if $$ \lim_{n\to\infty}\frac1n\sum_{j=1}^{n}y_{jn}=a, \qquad \lim_{n\to\infty}\frac1n\sum_{j=1}^{n}y_{jn}^{,2}=a^2, $$ then for every $\varepsilon>0$, $$ \lim_{n\to\infty} \frac1n #{j:1\le j\le n,\ |y_{jn}-a|\ge\varepsilon} =0. $$ Consider $$ \sum_{j=1}^{n}(y_{jn}-a)^2. $$ Expanding the square gives $$ \frac1n\sum_{j=1}^{n}(y_{jn}-a)^2 = \frac1n\sum_{j=1}^{n}y_{jn}^{,2} -\frac{2a}{n}\sum_{j=1}^{n}y_{jn} +a^2. $$ By the hypotheses, $$ \lim_{n\to\infty}...
TAOCP 3.5 Exercise 5
Section 3.5: What Is a Random Sequence? Exercise 5. ▶ [ HM22 ] Let $U_n = (2^{(9(n+1))/3}) \bmod 1$. What is $\Pr{U_n < \frac{1}{2}}$? Verified: yes Solve time: 1m11s Solution We are asked to determine $\Pr{U_n < \tfrac{1}{2}}$ for the sequence $U_n = \bigl(2^{9(n+1)/3}\bigr) \bmod 1.$ First, observe that $2^{9(n+1)/3} = 2^{3(n+1)} = 2^{3n+3} = 8 \cdot 2^{3n}.$ Hence we may write $U_n = (8 \cdot 2^{3n}) \bmod 1.$ Since...
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.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.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.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 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.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.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 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.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 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 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 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 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 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.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.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.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 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.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.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.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.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.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 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.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.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...
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 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.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.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.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.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 +...