#math-hard
TAOCP 3.4.1 Exercise 30
Section 3.4.1: Numerical Distributions Exercise 30. [ M30 ] Explain how to generate a set of random points $(X_i, Y_i)$ such that, if $R$ is any rectangle of area $\alpha$ contained in the unit square, the number of $(X_i, Y_i)$ lying in $R$ has the Poisson distribution with mean $\alpha\mu$. Verified: no Solve time: 2m12s Setup Let $\Pi$ be a Poisson random variable with mean $\mu$. Generate $\Pi=N$, then generate...
TAOCP 3.4.1 Exercise 25
Section 3.4.1: Numerical Distributions Exercise 25. [ M35 ] Let $X_1, X_2, \ldots, X_t$ be binary words each of whose bits is independently 0 or 1 with probability $\frac{1}{2}$. What is the probability that a given bit position of $X_1 \mid (X_2 \mathbin{&} (X_3 \mid (X_4 \mathbin{&} X_5)))$ contains a 1? Generalize. Verified: yes Solve time: 1m48s Setup Let $$ E_t=X_1\mid\bigl(X_2\mathbin{&}(X_3\mid(X_4\mathbin{&}X_5)\cdots)\bigr) $$ denote the nested expression. Since corresponding bit positions...
TAOCP 3.3.4 Exercise 30
Section 3.3.4: The Spectral Test Exercise 30. [ M33 ] (S. K. Zaremba.) Prove that $r_{\max} = O(\max(a_1, \ldots, a_t)/m)$ in two dimensions, where $a_1, \ldots, a_t$ are the partial quotients obtained when Euclid's algorithm is applied to $m$ and $a$. [ Hint: We have $a/m = /!!/a_1, \ldots, a_s/!!/$ in the notation of Section 4.5.3; apply exercise 4.5.3–42.] Verified: no Solve time: 3m25s Setup Let $(X_n)$ be a linear...
TAOCP 3.3.4 Exercise 28
Section 3.3.4: The Spectral Test Exercise 28. ▶ [ M28 ] (H. Niederreiter.) Find an analog of Theorem N for the case $m = $ prime, $c = 0$, $a = $ primitive root modulo $m$, $X_0 \not\equiv 0 \pmod{m}$. [ Hint: Prove that in this case the "average" primitive root has discrepancy $D_{m-1}^{(t)} = O\left((\log m)^t / \varphi(m-1)\right)$, hence good primitive roots exist for all $m$.] Verified: yes Solve...
TAOCP 3.3.4 Exercise 24
Section 3.3.4: The Spectral Test Exercise 24. ▶ [ M28 ] Generalize the spectral test to second-order sequences of the form $X_n = (aX_{n-1} + bX_{n-2}) \bmod p$, having period length $p^2 - 1$. (See Eq. 3.2.2–(8).) How should Algorithm S be modified? Verified: yes Solve time: 5m34s Exercise 3.3.4.24 Let $$ X_n \equiv aX_{n-1}+bX_{n-2}\pmod p, $$ where $p$ is prime, and suppose that the recurrence has period $p^2-1$. By...
TAOCP 3.3.4 Exercise 23
Section 3.3.4: The Spectral Test Exercise 23. [ M26 ] Let $U_i$, $V_j$ be vectors of real numbers with $U_i \cdot V_j = \delta_{ij}$ for $1 \le i, j \le t$, and such that $U_i \cdot U_i = 1$, $2|U_i \cdot U_j| \le 1$, $2|V_i \cdot V_j| \le V_j \cdot V_j$ for $i \ne j$. How large can $V_1 \cdot V_1$ be? (This question relates to the bounds in step...
TAOCP 3.3.4 Exercise 6
Section 3.3.4: The Spectral Test Exercise 6. [ M30 ] Let $a_0, a_1, \ldots, a_{t-1}$ be the partial quotients of $a/m$ as defined in Section 3.3.3, and let $A = \max_{0 \le j \le t} a_j$. Prove that $\mu_2 > 2\sqrt{A}/(A + 1 + 1/A)$. Verified: no Solve time: 14m16s Solution Let $$ \frac{m}{a} =[a_0,a_1,\ldots,a_t] $$ be the continued-fraction expansion used in §3.3.3, and let $$ A=\max_{0\le j\le t} a_j...
TAOCP 3.2.2 Exercise 31
Section 3.2.2: Other Methods Exercise 31. [ M30 ] (G. Marsaglia.) What is the period length of the sequence $\langle 7^n \rangle$ when $m = 2^e > 8$? Assume that $X_0, \ldots, X_{54}$ are not all $\equiv \pm 1 \pmod{8}$. Verified: no Solve time: 5m07s Exercise 3.2.2.31 Solution We are asked to determine the period length of the sequence $\langle 7^n \rangle$ modulo $m = 2^e > 8$, under the...
TAOCP 3.2.2 Exercise 17
Section 3.2.2: Other Methods Exercise 17. [ M33 ] (M. A. Martin, 1934.) Let $m$ and $k$ be positive integers, and let $X_1 = X_2 = \cdots = X_k = 0$. For all $n > 0$, set $X_{n+k}$ equal to the largest nonnegative value $< m$ such that the $k$-tuple $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ has not previously occurred in the sequence; in other words, $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ must differ...
TAOCP 3.2.2 Exercise 16
Section 3.2.2: Other Methods Exercise 16. ▶ [ M28 ] Let CONTENTS$(A)$ in method (10) be $(a_1 a_2 \ldots a_k)_2$ in binary notation. Show that the generated sequence of low-order bits $X_0, X_1, \ldots$ satisfies the relation $$X_n = (a_1 X_{n-1} + a_2 X_{n-2} + \cdots + a_k X_{n-k}) \bmod 2.$$ [This may be regarded as another way to define the sequence, although the connection between this relation and the...
TAOCP 3.2.2 Exercise 15
Section 3.2.2: Other Methods Exercise 15. [ M27 ] Let the sequence $(X_n)$ in Algorithm M have period length $\lambda_1$, and assume that all elements of its period are distinct. Let $q_0 = \min{r \mid r > 0 \text{ and } \lfloor Y_{n+r}/m \rfloor = \lfloor Y_n/m \rfloor}$. Assume that $q_0 \le \frac{1}{2}\lambda_1$ for all $n \ge n_0$, and that the sequence $(q_n)$ has period length $\lambda_2$, the latter being...
TAOCP 3.2.2 Exercise 12
Section 3.2.2: Other Methods Exercise 12. ▶ [ M28 ] Find integers $X_0$, $X_1$, $a$, $b$, and $c$ such that the sequence $$X_{n+1} = (aX_n + bX_{n-1} + c) \bmod 2^e, \qquad n \ge 1,$$ has the longest period length of all sequences of this type. [ Hint: It follows that $X_{n+2} = ((a+1)X_{n+1} + (b-a)X_n - bX_{n-1}) \bmod 2^e$; see exercise 11(c).] Verified: yes Solve time: 3m06s Exercise 3.2.2.12...
TAOCP 3.2.1.1 Exercise 14
Section 3.2.1.1: Choice of Modulus Exercise 14. [ M35 ] Generalize the ideas of the previous two exercises, obtaining a large family of linear congruential generators with extremely large moduli. Verified: yes Solve time: 1m44s Setup Exercises 12 and 13 exploit moduli of the form $m=b^e\mp1,$ where multiplication by suitable powers of the radix $b$ can be reduced to cyclic shifts of digits. Exercise 14 asks for a general formulation...
TAOCP 3.2.1.1 Exercise 10
Section 3.2.1.1: Choice of Modulus Exercise 10. [ M26 ] The solution to exercise 9(b) sometimes works also when $a^2 > m$. Exactly how many multipliers $a$ are there for which the intermediate results in that method never exceed $m$, for all $x$ between $0$ and $m$? Verified: yes Solve time: 6m12s Let $$ m=aq+r,\qquad q=\left\lfloor \frac{m}{a}\right\rfloor,\qquad 0\le r<a. $$ Exercise 9(b) computes $ax \bmod m$ by writing $$ x=q\left\lfloor...
TAOCP 3.2.1.1 Exercise 11
Section 3.2.1.1: Choice of Modulus Exercise 11. [ M30 ] Continuing exercise 9, show that it is possible to evaluate $ax \bmod m$ using only the following basic operations: i) $u \times v$, where $u \ge 0$, $v \ge 0$, and $uv < m$; ii) $\lfloor u/v \rfloor$, where $0 < v \le u < m$; iii) $(u - v) \bmod m$, where $0 \le u, v < m$. In...
TAOCP 3.2.1.1 Exercise 12
Section 3.2.1.1: Choice of Modulus Exercise 12. ▶ [ M28 ] Consider computations by pencil and paper or an abacus. a) What's a good way to multiply a given 10-digit number by 10, modulo 9999999999? b) Same question, but multiply instead by 9999999900 (modulo 9999999999). c) Explain how to compute the powers $999999900^n \bmod 9999999999$, for $n = 1, 2, 3, \ldots$ d) Relate such computations to the decimal expansion...
TAOCP 2.3.3 Exercise 13
Section 2.3.3: Other Representations of Trees Exercise 13. [ M29 ] Give an informal proof that at the beginning of step A8 of Algorithm A we always have EXP(P) = EXP(Q) and CV(UP(P)) = CV(UP(Q)) . (This fact is important to the proper understanding of that algorithm.) Verified: yes Solve time: 1m23s Setup Algorithm A adds two polynomials represented as trees. Let P and Q denote the current nodes in...
TAOCP 2.3.2 Exercise 22
Section 2.3.2: Binary Tree Representation of Trees Exercise 22. [ M26 ] If T and T' are trees, let us say T can be embedded in T' , written T ⊆ T' , if there is a one-to-one function f from the nodes of T into the nodes of T' such that f preserves both preorder and postorder. (In other words, u precedes v in preorder for T if and...
TAOCP 2.3.2 Exercise 19
Section 2.3.2: Binary Tree Representation of Trees Exercise 19. [ M35 ] A free lattice is a mathematical system, which (for the purposes of this exercise) can be simply defined as the set of all formulas composed of variables and two abstract binary operators " ∨ " and " ∧ ". A relation " X ⪰ Y " is defined between certain formulas X and Y in the free lattice...
TAOCP 2.3.3 Exercise 19
Section 2.3.3: Other Representations of Trees Exercise 19. [ M27 ] Instead of using SCOPE links in (5) , we could simply list the number of descendants of each node, in preorder: $$ \begin{array}{c|cccccccccc} \text{DESC} & 3 & 0 & 1 & 0 & 5 & 1 & 0 & 1 & 0 & 0\ \text{INFO} & A & B & C & K & D & E & H...
TAOCP 2.2.2 Exercise 11
Section 2.2.2: Sequential Allocation Exercise 11. [ M30 ] Generalize the argument of exercise 9 so that the first $t$ insertions in any stack cause no movement, while subsequent insertions are unaffected. Thus if $t = 2$, the sequence in exercise 9 specifies $0 + 0 + 0 + 0 + 0 + 3 + 0 + 0 + 3 + 6 = 12$ moves. What is the average total...
TAOCP 2.2.4 Exercise 16
Section 2.2.4: Circular Lists Exercise 16. [ M28 ] Estimate the running time of the subroutine in exercise 15 in terms of some relevant parameters. Verified: no Solve time: 1m25s Setup Let $p$ denote the number of nonzero terms of polynomial(P) , $q$ denote the number of nonzero terms of polynomial(Q) at entry, $m$ denote the number of nonzero terms of polynomial(M) . Exercise 15 asks for a subroutine implementing...
TAOCP 2.2.2 Exercise 10
Section 2.2.2: Sequential Allocation Exercise 10. [ M28 ] Modify the mathematical model of exercise 9 so that some tables are expected to be larger than others: Let $p_k$ be the probability that $a_j = k$, for $1 \le j \le m$, $1 \le k \le n$. Thus $p_1 + p_2 + \cdots + p_n = 1$; the previous exercise considered the special case $p_k = 1/n$ for all $k$....
TAOCP 2.2.2 Exercise 18
Section 2.2.2: Sequential Allocation Exercise 18. [ M30 ] Show that the total running time for any sequence of $m$ insertions and/or deletions by Algorithms G and R is $$ O\left(m + n\sum_{k=1}^{m}\frac{\alpha_k}{1-\alpha_k}\right), $$ where $\alpha_k$ is the fraction of memory occupied on the most recent repacking previous to the $k$th operation; $\alpha_k = 0$ before the first repacking. (Therefore if the memory never gets more than, say, 90% full,...
TAOCP 2.2.2 Exercise 12
Section 2.2.2: Sequential Allocation Exercise 12. [ M28 ] The advantage of having two tables coexist in memory by growing towards each other, rather than by having them kept in separate independently bounded areas, may be quantitatively estimated (to a certain extent) as follows. Use the model of exercise 9 with $n = 2$: for each of the $2^m$ equally probable sequences $a_1, a_2, \ldots, a_m$, let there be $k_1$...
TAOCP 2.2.1 Exercise 5
Section 2.2.1: Stacks, Queues, and Deques Exercise 5. [ M28 ] Show that it is possible to obtain a permutation $p_1 p_2 \ldots p_n$ from $12\ldots n$ using a stack if and only if there are no indices $i < j < k$ such that $p_j < p_k < p_i$. Verified: no Solve time: - Setup Let $p_1p_2\ldots p_n$ be a permutation of $1,2,\ldots,n$. A permutation is said to be...
TAOCP 1.4.4 Exercise 19
Section 1.4.4: Input and Output Exercise 19. [ M28 ] Special considerations arise when input or output involves short blocks on a rotating device like a magnetic disk. Suppose a program works with $n \geq 2$ consecutive blocks of information in the following way: Block $k$ begins to be input at time $t_k$, where $t_1 = 0$. It is assigned for processing at time $u_k \geq t_k + T$ and...
TAOCP 2.2.2 Exercise 9
Section 2.2.2: Sequential Allocation Exercise 9. [ M27 ] Using the mathematical model described near the end of the text, prove that Eq. (14) is the expected number of moves. (Note that the sequence 1, 1, 4, 2, 3, 1, 2, 4, 2, 1 specifies $0 + 0 + 0 + 1 + 1 + 3 + 2 + 0 + 3 + 6 = 16$ moves.) Verified: no Solve...
TAOCP 2.2.1 Exercise 4
Section 2.2.1: Stacks, Queues, and Deques Exercise 4. [ M34 ] Find a simple formula for $a_n$, the number of permutations on $n$ elements that can be obtained with a stack like that in exercise 2. Verified: no Solve time: - Setup Let $a_n$ denote the number of permutations of ${1,2,\ldots,n}$ obtainable by a stack of the type described in exercise 2. By exercise 3, each obtainable permutation corresponds to...
TAOCP 1.3.3 Exercise 14
Section 1.3.3: Applications to Permutations Exercise 14. [ M34 ] Find the average value of the quantity $A$ in the timing of Algorithm $J$. Verified: yes Solve time: 24m50s Let $A$ denote the total number of executions of the assignment $$ j\leftarrow i $$ in Algorithm $J$. We compute the average of $A$ over all $n!$ permutations. 1. Contribution of a single cycle Let the permutation $\pi$ contain a cycle...
TAOCP 1.3.3 Exercise 37
Section 1.3.3: Applications to Permutations Exercise 37. [ M26 ] ( Even permutations. ) Let $\pi$ be a permutation of ${1,\ldots,n}$. Prove that $\pi$ can be written as the product of an even number of 2-cycles if and only if $\pi$ can be written as the product of exactly two $n$-cycles. Verified: no Solve time: 3m09s The forward direction is correct and standard. The reverse direction fails because it does...
TAOCP 1.3.3 Exercise 12
Section 1.3.3: Applications to Permutations Exercise 12. [ M27 ] ( Transposing a rectangular matrix .) Suppose an $m \times n$ matrix $(a_{ij})$, $m \ne n$, is stored in memory in a fashion like that of exercise 1.3.2-10, so that the value of $a_{ij}$ appears in location $L + n(i - 1) + (j - 1)$, where $L$ is the location of $a_{11}$. The problem is to find a way...
TAOCP 1.3.3 Exercise 18
Section 1.3.3: Applications to Permutations Exercise 18. [ M27 ] What is $p_{nkm}$, the probability that a permutation of $n$ objects has exactly $k$ cycles of length $m$? What is the corresponding generating function $G_{nm}(z)$? What is the average number of $m$-cycles and what is the standard deviation? (The text considers only the case $m = 1$.) Verified: yes Solve time: 16m52s Setup Let $p_{nkm}$ denote the probability that a...
TAOCP 1.3.3 Exercise 35
Section 1.3.3: Applications to Permutations Exercise 35. [ M30 ] Continuing the previous exercise, let $x_0x_1\ldots x_{l+m+n-1} = \alpha\beta\gamma$ where $\alpha$, $\beta$, and $\gamma$ are strings of respective lengths $l$, $m$, and $n$, and suppose that we want to change $\alpha\beta\gamma$ to $\gamma\beta\alpha$. Show that the corresponding permutation has a convenient cycle structure that leads to an efficient algorithm. [Exercise 34 considered the special case $m = 0$.] Hint: Consider...
TAOCP 1.3.3 Exercise 33
Section 1.3.3: Applications to Permutations Exercise 33. [ M33 ] If $m = 2^{2^l}$ and $n = 2^{2l+1}$, show how to construct sequences of permutations $(\alpha_{j1}, \alpha_{j2}, \ldots, \alpha_{jn}; \beta_{j1}, \beta_{j2}, \ldots, \beta_{jn})$ for $0 \le j < m$ with the following "orthogonality" property: $$ \alpha_{i1}\beta_{j1}\alpha_{i2}\beta_{j2}\cdots\alpha_{in}\beta_{jn} = \begin{cases} (1,2,3,4,5), & \text{if } i = j;\ (), & \text{if } i \ne j. \end{cases} $$ Each $\alpha_{jk}$ and $\beta_{jk}$ should be...
TAOCP 1.3.3 Exercise 10
Section 1.3.3: Applications to Permutations Exercise 10. [ M28 ] Examine the timing characteristics of Program $B$, namely, the quantities $A$, $B$, $\ldots$, $Z$ shown there; express the total time in terms of the quantities $X$, $Y$, $M$, $N$, $U$, $V$ defined in (19), and of $F$. Compare the total time for Program $B$ with the total time for Program $A$ on the input (6), as computed in exercise 7....
TAOCP 1.2.9 Exercise 23
Section 1.2.9: Generating Functions Exercise 23. [ M33 ] (L. Carlitz.) (a) Prove that for all integers $m \ge 1$ there are polynomials $f_m(z_1,\ldots,z_m)$ and $g_m(z_1,\ldots,z_m)$ such that the formula $$ \sum_{k_1,\ldots,k_m \ge 0} \binom{r}{n-k_1}\binom{k_1}{n-k_2}\cdots\binom{k_{m-1}}{n-k_m} z_1^{k_1}\cdots z_m^{k_m} = f_m(z_1,\ldots,z_m)^{,n-r} g_m(z_1,\ldots,z_m)^{,r} $$ is an identity for all integers $n \ge r \ge 0$. (b) Generalizing exercise 15, find a closed form for the sum $$ S_n(z_1,\ldots,z_m) = \sum_{k_1,\ldots,k_m \ge 0} \binom{k_1}{n-k_2}\binom{k_2}{n-k_3}\cdots\binom{k_m}{n-k_1}...
TAOCP 1.3.3 Exercise 6
Section 1.3.3: Applications to Permutations Exercise 6. [ M28 ] What changes are made to the timing of Program $A$ if we remove the assumption that all blank words occur at the extreme right? Verified: yes Solve time: 1m21s Setup We are asked to determine the effect on the execution timing of Program $A$ if the assumption that all blank words appear at the extreme right of the input is...
TAOCP 1.2.9 Exercise 15
Section 1.2.9: Generating Functions Exercise 15. [ M28 ] By considering $H(w)=\sum_{n \ge 0} G_n(z)w^n$, find a closed form for the generating function $$ G_n(z) = \sum_{k=0}^{n} \binom{n-k}{k} z^k = \sum_{k=0}^{n} \binom{2k-n-1}{k} (-z)^k. $$ Verified: yes Solve time: 1m26s Setup Define $$ G_n(z)=\sum_{k=0}^{n}\binom{n-k}{k}z^k. $$ Define the ordinary generating function in $n$ $$ H(w)=\sum_{n\ge 0} G_n(z)w^n. $$ The task is to determine a closed form for $H(w)$. Solution Write $$ G_n(z)=\sum_{k\ge...
TAOCP 1.2.8 Exercise 36
Section 1.2.8: Fibonacci Numbers Exercise 36. [ M32 ] ( Fibonacci strings. ) Let $S_1=\text{"a"}$, $S_2=\text{"b"}$, and $S_{n+2}=S_{n+1}S_n$, $n>0$; in other words, $S_{n+2}$ is formed by placing $S_n$ at the right of $S_{n+1}$. We have $S_3=\text{"ba"}$, $S_4=\text{"bab"}$, $S_5=\text{"babba"}$, etc. Clearly $S_n$ has $F_n$ letters. Explore the properties of $S_n$. (Where do double letters occur? Can you predict the value of the $k$th letter of $S_n$? What is the density of...
TAOCP 1.2.8 Exercise 12
Section 1.2.8: Fibonacci Numbers Exercise 12. [ M26 ] The "second order" Fibonacci sequence is defined by the rule $$ \mathcal{F} 0 = 0, \qquad \mathcal{F} 1 = 1, \qquad \mathcal{F} {n+2} = \mathcal{F} {n+1} + \mathcal{F}_n + F_n. $$ Express $\mathcal{F} n$ in terms of $F_n$ and $F {n+1}$. [Hint: Use generating functions.] Verified: no Solve time: - Setup Let $$ \mathcal{G}(z)=\sum_{n\ge0}\mathcal{F}_n z^n $$ be the generating function for...
TAOCP 1.2.8 Exercise 42
Section 1.2.8: Fibonacci Numbers Exercise 42. [ M26 ] (D. A. Klarner.) Show that if $m$ and $n$ are nonnegative integers, there is a unique sequence of indices $k_1 \gg k_2 \gg \cdots \gg k_r$ such that $$ m = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, \qquad n = F_{k_1+1} + F_{k_2+1} + \cdots + F_{k_r+1}. $$ (See exercise 34. The $k$'s may be negative, and $r$ may be...
TAOCP 1.2.8 Exercise 19
Section 1.2.8: Fibonacci Numbers Exercise 19. [ M27 ] What is $\cos 36^\circ$? Verified: yes Solve time: 44s Setup Determine the exact value of $\cos 36^\circ$. Equation (4) states that $$ F_{n+1}F_{n-1}-F_n^2=(-1)^n. \tag{4} $$ Taking $n=2$ gives $$ F_3F_1-F_2^2=1, $$ which is $2\cdot1-1^2=1$. Exercise 17 generalizes (4) to F_{n+k}F_{m-k}-F_nF_m = (-1)^nF_{m-n-k}F_k. ] Taking $n=2$, $m=5$, $k=1$ yields F_3F_4-F_2F_5 F_2F_1, $$ hence $$ 2\cdot3-1\cdot5=1. $$ Therefore $$ F_5=F_4+F_3=3+2=5. The numbers $1,2,3,5$...
TAOCP 1.2.8 Exercise 14
Section 1.2.8: Fibonacci Numbers Exercise 14. [ M28 ] Let $m$ be a fixed positive integer. Find $a_n$, given that $$ a_0 = 0, \qquad a_1 = 1, \qquad a_{n+2} = a_{n+1} + a_n + \binom{n}{m}, \quad n \ge 0. $$ Verified: yes Solve time: 54s Setup We are asked to find a closed-form expression for the sequence $\langle a_n \rangle$ defined by $$ a_0 = 0, \qquad a_1 =...
TAOCP 1.2.8 Exercise 37
Section 1.2.8: Fibonacci Numbers Exercise 37. [ M35 ] (R. E. Gaskell, M. J. Whinihan.) Two players compete in the following game: There is a pile containing $n$ chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding...
TAOCP 1.2.7 Exercise 18
Section 1.2.7: Harmonic Numbers Exercise 18. [ M33 ] (J. Selfridge.) What is the highest power of $2$ that divides the numerator of $1 + \frac{1}{3} + \cdots + \frac{1}{2n-1}$? Verified: no Solve time: - Setup Let $$ S_n = 1 + \frac13 + \frac15 + \cdots + \frac{1}{2n-1}. $$ Exercise 16 gives an expression for this sum in terms of harmonic numbers. Since $$ H_{2n} = \sum_{k=1}^{2n}\frac1k = \sum_{k=1}^{n}\frac{1}{2k-1}...
TAOCP 1.2.7 Exercise 19
Section 1.2.7: Harmonic Numbers Exercise 19. [ M30 ] List all nonnegative integers $n$ for which $H_n$ is an integer. Verified: no Solve time: - Setup Let $$ H_n=\sum_{k=1}^{n}\frac{1}{k}, \qquad H_0=0. $$ We seek all nonnegative integers $n$ for which $H_n$ is an integer. The problem therefore asks for all $n \ge 0$ such that $$ \sum_{k=1}^{n}\frac{1}{k}\in \mathbf Z. $$ We will prove that the only such values are $$...
TAOCP 1.2.6 Exercise 63
Section 1.2.6: Binomial Coefficients Exercise 63. [ M30 ] If $l,m,n$ are integers and $n \ge 0$, prove that $$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$ Verified: no Solve time: - Setup We must prove that, for integers $l,m,n$ with $n \ge 0$, $$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$ All sums extend over all integers $j,k$. Since the binomial coefficients vanish outside their natural ranges, only finitely many terms...
TAOCP 1.2.7 Exercise 22
Section 1.2.7: Harmonic Numbers Exercise 22. [ M28 ] Evaluate $\sum_{k=0}^{n} H_k H_{n-k}$. Verified: no Solve time: - Setup Let $$ S_n=\sum_{k=0}^{n} H_kH_{n-k}. $$ Since $H_0=0$, the terms with $k=0$ and $k=n$ vanish, hence $$ S_n=\sum_{k=1}^{n-1}H_kH_{n-k}. $$ The problem is to evaluate $S_n$ in closed form. We will prove that $$ S_n=(n+1)\bigl(H_n^2-H_n^{(2)}\bigr)-2nH_n+2n, $$ where $$ H_n^{(2)}=\sum_{j=1}^{n}\frac{1}{j^2}. $$ Solution Expand one harmonic number: $$ H_{n-k}=H_n-\sum_{j=n-k+1}^{n}\frac{1}{j}. $$ Therefore $$ S_n =\sum_{k=0}^{n}H_k \left(...
TAOCP 1.2.4 Exercise 45
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 45. ▶ [ M28 ] The result of exercise 37 is somewhat surprising, since it implies that $$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \sum_{0 \le k < m} \left\lfloor \frac{nk+x}{m} \right\rfloor $$ when $m$ and $n$ are positive integers and $x$ is arbitrary. This “reciprocity relationship” is one of many similar formulas (see Section 3.3.3). Show that...
TAOCP 1.2.4 Exercise 30
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 30. [ M30 ] Prove that the function $\varphi(n)$ of exercise 27 is multiplicative. Using this fact, evaluate $\varphi(1000000)$, and give a method for evaluating $\varphi(n)$ in a simple way once $n$ has been factored into primes. Verified: yes Solve time: 36s Setup Let $n$ be a positive integer and let $\varphi(n)$ denote the number of integers in ${0,1,\ldots,n-1}$ that are...
TAOCP 1.2.4 Exercise 46
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 46. [ M29 ] ( General reciprocity law. ) Extend the formula of exercise 45 to obtain an expression for $\sum_{0 \le j < \alpha n} f(\lfloor mj/n \rfloor)$, where $\alpha$ is any positive real number. Verified: yes Solve time: 1m10s Setup Let $$ S(\alpha)=\sum_{0\le j<\alpha n} f!\left(\left\lfloor \frac{mj}{n}\right\rfloor\right), $$ where $m,n>0$ are integers and $\alpha>0$ is real. Exercise 45 corresponds...
TAOCP 1.2.4 Exercise 38
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 38. [ M26 ] (E. Busche, 1909.) Prove that, for all real $x$ and $y$ with $y>0$, $$ \sum_{0 \le k < y} \left\lfloor x+\frac{k}{y} \right\rfloor = \lfloor xy + \lfloor x+1 \rfloor(\lceil y \rceil - y)\rfloor. $$ In particular, when $y$ is a positive integer $n$, we have the important formula $$\lfloor x \rfloor + \left\lfloor x+\frac1n \right\rfloor + \cdots...
TAOCP 1.2.4 Exercise 37
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 37. ▶ [ M30 ] Let $m$ and $n$ be integers, $n>0$. Show that $$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \frac{(m-1)(n-1)}{2} + \frac{d-1}{2} + d\left\lfloor \frac{x}{d} \right\rfloor, $$ where $d$ is the greatest common divisor of $m$ and $n$, and $x$ is any real number. Verified: yes Solve time: 11m54s Let $$ S(x)=\sum_{k=0}^{n-1}\left\lfloor \frac{mk+x}{n}\right\rfloor, $$ where $m,n\in\mathbb...
TAOCP 1.2.3 Exercise 46
Section 1.2.3: Sums and Products Exercise 46. ▶ [ M30 ] Let $A$ be an $m \times n$ matrix, and let $B$ be an $n \times m$ matrix. Given that $1 \le j_1, j_2, \ldots, j_m \le n$, let $A_{j_1 j_2 \ldots j_m}$ denote the $m \times m$ matrix consisting of columns Verified: no Solve time: 11m02s Let $$ A=(a_{ik}) {1\le i\le m,\ 1\le k\le n}, \qquad B=(b {kj})_{1\le k\le...
TAOCP 1.2.3 Exercise 29
Section 1.2.3: Sums and Products Exercise 29. ▶ [ M30 ] (a) Express $\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k$ in terms of the multiple-sum notation explained at the end of the section. (b) Express the same sum in terms of $\sum_{i=0}^n a_i$, $\sum_{i=0}^n a_i^2$, and $\sum_{i=0}^n a_i^3$ [see Eq. (13)]. Verified: yes Solve time: 38s Setup Define $$ S=\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k. $$ Part (a) asks for an...
TAOCP 1.2.3 Exercise 44
Section 1.2.3: Sums and Products Exercise 44. ▶ [ M26 ] What is the sum of all $n^2$ elements in the inverse of Cauchy’s matrix? Verified: yes Solve time: 3m29s Let $$ A=(a_{ij}) {1\le i,j\le n}, \qquad a {ij}=\frac1{x_i+y_j}, $$ be Cauchy's matrix, and let $B=A^{-1}=(b_{ij})$. From Exercise 41, $$ b_{ij} = \frac{ \displaystyle \prod_{k=1}^{n}(x_j+y_k)(x_k+y_i) }{ (x_j+y_i) \displaystyle \prod_{k\ne j}(x_j-x_k) \displaystyle \prod_{k\ne i}(y_i-y_k) }. $$ We seek $$ S=\sum_{i=1}^n\sum_{j=1}^n b_{ij}....
TAOCP 1.2.3 Exercise 33
Section 1.2.3: Sums and Products Exercise 33. ▶ [ M30 ] One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those of exercise 20: $$ \begin{aligned} \frac{1}{(a-b)(a-c)} + \frac{1}{(b-a)(b-c)} + \frac{1}{(c-a)(c-b)} &= 0, \[5pt] \frac{a}{(a-b)(a-c)} + \frac{b}{(b-a)(b-c)} + \frac{c}{(c-a)(c-b)} &= 0, \[5pt] \frac{a^2}{(a-b)(a-c)} + \frac{b^2}{(b-a)(b-c)} + \frac{c^2}{(c-a)(c-b)} &= 1, \[5pt] \frac{a^3}{(a-b)(a-c)} + \frac{b^3}{(b-a)(b-c)} + \frac{c^3}{(c-a)(c-b)} &= a+b+c. \end{aligned} $$ Prove that these formulas...
TAOCP 1.2.3 Exercise 41
Section 1.2.3: Sums and Products Exercise 41. [ M26 ] Show that the inverse of Cauchy’s matrix is given by $$b_{ij} = \left( \prod_{1 \le k \le n} (x_j + y_k)(x_k + y_i) \right) \bigg/ (x_j + y_i) \left( \prod_{\substack{1 \le k \le n \ k \ne j}} (x_j - x_k) \right) \left( \prod_{\substack{1 \le k \le n \ k \ne i}} (y_i - y_k) \right).$$ Verified: yes Solve time:...
TAOCP 1.2.2 Exercise 26
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 26. [ M27 ] Find a rigorous upper bound on the error made by the algorithm in the previous exercise, based on the precision used in the arithmetic operations. Verified: no Solve time: 29s Setup Let the computer work with fixed precision $\delta > 0$, meaning that every right shift and every subtraction is performed with an error whose absolute value is at...
TAOCP 1.2.2 Exercise 28
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 28. [ M30 ] (R. Feynman.) Develop a method for computing $b^x$ when $0 \le x < 1$, using only shifting, addition, and subtraction (similar to the algorithm in exercise 25), and analyze its accuracy. Verified: no Solve time: 27s Setup Let $0 \le x < 1,$ and let $b>0$, $b\ne1$. We seek a procedure for computing $b^x,$ using only shifting, addition, and...
TAOCP 1.2.10 Exercise 17
Section 1.2.10: Analysis of an Algorithm Exercise 17. [ M27 ] Let $f(z)$ and $g(z)$ be generating functions that represent probability distributions. a) Show that $h(z)=g(f(z))$ is also a generating function representing a probability distribution. b) Interpret the significance of $h(z)$ in terms of $f(z)$ and $g(z)$. c) Give formulas for the mean and variance of $h$ in terms of those for $f$ and $g$. Verified: yes Solve time: 1m06s...
TAOCP 1.2.10 Exercise 7
Section 1.2.10: Analysis of an Algorithm Exercise 7. [ M27 ] In our analysis of Algorithm M, we assumed that all the $X[k]$ were distinct. Suppose, instead, that we make only the weaker assumption that $X[1],X[2],\ldots,X[n]$ contain precisely $m$ distinct values; the values are otherwise random, subject to this constraint. What is the probability distribution of $A$ in this case? Verified: yes Solve time: 4m19s Exercise 1.2.10.7 (Corrected Solution) We...
TAOCP 1.2.1 Exercise 11
Section 1.2.1: Mathematical Induction Exercise 11. [ M30 ] Find and prove a simple formula for the sum $$ \frac{1^3}{1^4 + 4} - \frac{3^3}{3^4 + 4} + \frac{5^3}{5^4 + 4} - \cdots + \frac{(-1)^n(2n + 1)^3}{(2n + 1)^4 + 4}. $$ Verified: no Solve time: 4m32s Let $$ S_n=\sum_{k=0}^{n}(-1)^k\frac{(2k+1)^3}{(2k+1)^4+4}. $$ We seek a closed form for $S_n$. The reviewer correctly pointed out that the previous partial-fraction decomposition was false. Therefore...
TAOCP 1.2.10 Exercise 18
Section 1.2.10: Analysis of an Algorithm Exercise 18. [ M28 ] Suppose that the values taken on by $X[1],X[2],\ldots,X[n]$ in Algorithm M include exactly $k_1$ ones, $k_2$ twos, $\ldots$, $k_n$ $n$'s, arranged in random order, where $$ k_1+k_2+\cdots+k_n = n. $$ Show that in this generalized situation, the generating function (8) becomes $$ \left(\frac{k_n z}{k_n}\right) \left(\frac{k_{n-1}z+k_n}{k_{n-1}+k_n}\right) \left(\frac{k_{n-2}z+k_{n-1}+k_n}{k_{n-2}+k_{n-1}+k_n}\right)\cdots \left(\frac{k_1z+k_2+\cdots+k_n}{k_1+k_2+\cdots+k_n}\right)z, $$ using the convention $0/0=1$. Verified: yes Solve time: 2m32s The critical...