#math-medium
TAOCP 3.4.1 Exercise 29
Section 3.4.1: Numerical Distributions Exercise 29. [ M20 ] (J. L. Bentley and J. B. Saxe.) Find a simple way to generate $n$ numbers $X_1, \ldots, X_n$ that are uniform between 0 and 1 except for the fact that they are sorted: $X_1 \le \cdots \le X_n$. Your algorithm should take only $O(n)$ steps. Verified: yes Solve time: 1m31s Solution We want $X_1 \le X_2 \le \cdots \le X_n$ such...
TAOCP 3.4.1 Exercise 26
Section 3.4.1: Numerical Distributions Exercise 26. [ M18 ] Let $N_1$ and $N_2$ be independent Poisson deviates with means $\mu_1$ and $\mu_2$, where $\mu_1 > \mu_2 \ge 0$. Prove or disprove: (a) $N_1 + N_2$ has the Poisson distribution with mean $\mu_1 + \mu_2$. (b) $N_1 - N_2$ has the Poisson distribution with mean $\mu_1 - \mu_2$. Verified: yes Solve time: 3m28s Solution Let $N_1$ and $N_2$ be independent Poisson...
TAOCP 3.4.1 Exercise 20
Section 3.4.1: Numerical Distributions Exercise 20. [ M20 ] Let $A$ be the area of the shaded region in Fig. 13, and let $R$ be the area of the enclosing rectangle. Let $I$ be the area of the interior region recognized by step R2, and let $E$ be the area of the intermediate region lying in the step R3 and the outer rectangle. Determine the number of times each step...
TAOCP 3.4.1 Exercise 18
Section 3.4.1: Numerical Distributions Exercise 18. [ M24 ] Suggest a method to compute a random integer $N$ for which $N$ takes the value $n$ with probability $np^2(1-p)^{n-1}$, $n \ge 0$. (The case of particular interest is when $p$ is rather small.) Verified: yes Solve time: 4m33s Exercise 3.4.1.18 [ M24 ] We are asked to generate a random integer $N$ such that $$ \Pr{N=n} = n p^2 (1-p)^{,n-1}, \qquad...
TAOCP 3.4.1 Exercise 17
Section 3.4.1: Numerical Distributions Exercise 17. ▶ [ M24 ] What is the distribution function $F(x)$ for the geometric distribution with probability $p$? What is the generating function $G(z)$? What are the mean and standard deviation of this distribution? Verified: yes Solve time: 1m33s Solution Let $X$ be a random variable representing the number of trials until the first success in a sequence of independent Bernoulli trials with success probability...
TAOCP 3.4.1 Exercise 4
Section 3.4.1: Numerical Distributions Exercise 4. [ M20 ] Prove the two relations in (8). Verified: no Solve time: 3m28s Correctness The solution does not answer the exercise as stated. The exercise concerns the two-dimensional spectral test of Section 3.3.4 and asks for a proof that $$ r_{\max}=O!\left(\frac{\max(a_1,\ldots,a_s)}{m}\right), $$ where $a_1,\ldots,a_s$ are the partial quotients in the continued fraction expansion of $a/m$, using the hint that refers to Exercise 4.5.3-42....
TAOCP 3.4.1 Exercise 2
Section 3.4.1: Numerical Distributions Exercise 2. [ M16 ] Assuming that $mU$ is a random integer between 0 and $m - 1$, what is the exact probability that $\lfloor kU \rfloor = r$, if $0 \le r < k$? Compare this with the desired probability $1/k$. Verified: yes Solve time: 1m26s Solution Let $U$ be a random variable uniformly distributed on $[0,1)$, and suppose that $mU$ is interpreted as a...
TAOCP 3.3.4 Exercise 32
Section 3.3.4: The Spectral Test Exercise 32. ▶ [ M21 ] Let $m_1 = 2^{31} - 1$ and $m_2 = 2^{31} - 249$ be the moduli of generator (38). a) Show that if $U_n = (X_n/m_1 - Y_n/m_2) \bmod 1$, we have $U_n \approx Z_n/m_1$. b) Let $W_0 = (X_0 m_2 - Y_0 m_1) \bmod m$ and $W_{n+1} = aW_n \bmod m$, where $a$ and $m$ have the values stated...
TAOCP 3.3.4 Exercise 26
Section 3.3.4: The Spectral Test Exercise 26. [ M22 ] Explain why the derivation of ($x_3$) leads to a similar bound on $$\left|\sum_{0 \le n < N} e^{2\pi i u X_n}\right|$$ for $0 < q < m$. Verified: no Solve time: 3m33s Solution Consider a linear congruential sequence $(X_n)$ defined by $X_{n+1} = (a X_n + c) \bmod m, \quad 0 \le X_n < m,$ with full period length $m$....
TAOCP 3.3.4 Exercise 20
Section 3.3.4: The Spectral Test Exercise 20. [ M23 ] Discuss how to carry out an appropriate spectral test for linear congruential sequences having $c = 0$, $X_0$ odd, $m = 2^e$, $a \bmod 8 = 3$ or $5$. (See exercise 3.2.1.2–9.) Verified: yes Solve time: 1m31s Solution Let $X_{n+1} \equiv aX_n \pmod{2^e}, \qquad X_0 \text{ odd}, \qquad a \equiv 3 \text{ or } 5 \pmod 8.$ By exercise 3.2.1.2-9,...
TAOCP 3.3.4 Exercise 3
Section 3.3.4: The Spectral Test Exercise 3. [ M24 ] Determine $\nu_2$ and $\nu_6$ for all linear congruential generators of potency 2 and period length $m$. Verified: yes Solve time: 8m50s Solution Let $b=a-1$. For a linear congruential generator of period length $m$ and potency $2$, $b^2\equiv0\pmod m,\qquad b\not\equiv0\pmod m.$ By the theory of the spectral test, $\nu_t$ is the minimum Euclidean length of a nonzero integer vector $(u_1,\ldots,u_t)$ satisfying...
TAOCP 3.2.2 Exercise 2
Section 3.2.2: Other Methods Exercise 2. [ M20 ] A good source of random numbers will have $X_{n-1} < X_{n+1} < X_n$ about one-sixth of the time, since each of the six possible relative orders of $X_{n-1}$, $X_n$, and $X_{n+1}$ should be equally probable. However, show that the ordering above never occurs if the Fibonacci sequence (5) is used. Verified: yes Solve time: 1m40s Solution Let $m = p_1 p_2...
TAOCP 3.3.2 Exercise 5
Section 3.3.2: Empirical Tests Exercise 5. [ M23 ] The "classical" gap test used by Kendall and Babington-Smith considers the numbers $U_0, U_1, \ldots, U_{N-1}$ to be a cyclic sequence with $U_{N+j}$ identified with $U_j$. Here $N$ is a fixed number of $U$'s that are to be subjected to the test. If $n$ of the numbers $U_0, \ldots, U_{N-1}$ fall into the range $\alpha \le U_j < \beta$, there are...
TAOCP 3.3.2 Exercise 3
Section 3.3.2: Empirical Tests Exercise 3. ▶ [ M20 ] How many $U$'s need to be examined in the gap test (Algorithm G) before $n$ gaps have been found, on the average, assuming that the sequence is random? What is the standard deviation of this quantity? Verified: yes Solve time: 1m55s Solution Let $N$ be the total number of values $U_j$ examined by Algorithm G when $n$ gaps have been...
TAOCP 3.3.1 Exercise 7
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 7. [ M16 ] Prove that $K_n^+$ and $K_n^-$ can never be negative. What is the largest possible value $K_n^-$ can have? Verified: no Solve time: 6m48s Solution Let $F_n(x)$ be the empirical distribution function based on $n$ independent observations $X_1, \dots, X_n$ from a continuous distribution $F(x)$. Recall the definitions of the Kolmogorov statistics: $$ K_n^+ = \sup_x \bigl(F_n(x)...
TAOCP 3.3.1 Exercise 6
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 6. [ M20 ] Consider $F_n(x)$, as given in Eq. (10), for fixed $x$. What is the probability that $F_n(x) = s/n$, given an integer $s$? What is the mean value of $F_n(x)$? What is the standard deviation? Verified: yes Solve time: 2m41s Solution Let $F_n(x)$ be the empirical distribution function defined by equation (10) of Section 3.3.1: $F_n(x) =...
TAOCP 3.2.2 Exercise 36
Section 3.2.2: Other Methods Exercise 36. [ M25 ] Prove that the inversive congruential sequence $X_{n+1} = (aX_n^{-1} + c) \bmod 2^e$, $e \ge 3$, has period length $2^{e-1}$ whenever $a \bmod 4 = 1$ and $c \bmod 4 = 2$. Verified: yes Solve time: 1m31s Solution We consider the inversive congruential sequence defined by $X_{n+1} \equiv a X_n^{-1} + c \pmod{2^e}, \qquad e \ge 3, \eqno(1)$ where $a \bmod...
TAOCP 3.2.2 Exercise 34
Section 3.2.2: Other Methods Exercise 34. [ M25 ] Prove that the inversive congruential sequence (12) has period $p + 1$ if and only if the polynomial $f(x) = x^2 - cx - a$ has the following two properties: (i) $x^{p+1} \bmod f(x)$ is a nonzero constant, when computed with polynomial arithmetic modulo $p$; (ii) $x^{(p+1)/q} \bmod f(x)$ has degree 1 for every prime $q$ that divides $p+1$. [ Hint:...
TAOCP 3.2.2 Exercise 33
Section 3.2.2: Other Methods Exercise 33. ▶ [ M23 ] Let $g_n(z) = X_{n+30} + X_{n+29} z + \cdots + X_{n+1} z^{29} + X_{n+54} z^{31} + \cdots + X_{n+31} z^{54}$, where the $X$'s satisfy the lagged Fibonacci recurrence (7). Find a simple relation between $g_n(z)$ and $g_{n+1}(z)$. (b) Express $X_{500}$ in terms of $X_1, \ldots, X_{55}$. Verified: yes Solve time: 1m23s Solution The sequence $\langle X_n \rangle$ satisfies the lagged...
TAOCP 3.2.2 Exercise 32
Section 3.2.2: Other Methods Exercise 32. [ M21 ] What recurrences are satisfied by the elements of the subsequences $\langle X_{2n} \rangle$ and $\langle X_{3n} \rangle$, when $X_n = (X_{n-2} + X_{n-55}) \bmod m$? Verified: yes Solve time: 2m29s Solution Let $$ X_n \equiv X_{n-2}+X_{n-55}\pmod m . $$ Introduce the shift operator $E$, where $E(X_n)=X_{n+1}$. Then the recurrence may be written $$ (1-E^{-2}-E^{-55})X_n=0 . $$ Equivalently, $$ (E^{55}-E^{53}-1)X_n=0 . $$...
TAOCP 3.2.2 Exercise 18
Section 3.2.2: Other Methods Exercise 18. [ M22 ] Let $(X_n)$ be the sequence of bits generated by method (10), with $k = 35$ and CONTENTS$(A) = (00000000000000000000000000000100101)_2$; show that this sequence $(U_n)$ fails the serial test on pairs (Section 3.3.2(ii)) when $d = 8$. Verified: no Solve time: 4m27s Solution We are asked to show that the sequence of $8$-bit blocks $$ U_n = (X_{8n}, X_{8n+1}, \dots, X_{8n+7}) $$...
TAOCP 3.2.2 Exercise 13
Section 3.2.2: Other Methods Exercise 13. [ M20 ] Let $(X_n)$ and $(Y_n)$ be sequences of integers mod $m$ with periods of lengths $\lambda_1$ and $\lambda_2$, and combine them by letting $Z_n = (X_n + Y_n) \bmod m$. Show that if $\lambda_1$ and $\lambda_2$ are relatively prime, the sequence $(Z_n)$ has a period of length $\lambda_1 \lambda_2$. Verified: no Solve time: 4m54s Corrected Solution Let $(X_n)$ and $(Y_n)$ be sequences...
TAOCP 3.2.2 Exercise 14
Section 3.2.2: Other Methods Exercise 14. [ M24 ] Let $X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, $\lambda_3$ be as in the previous exercise. Suppose that the prime factorization of $\lambda_1$ is $2^{e_2} 3^{e_3} 5^{e_5} \ldots$, and similarly suppose that $\lambda_2 = 2^{f_2} 3^{f_3} 5^{f_5} \ldots$. Let $g_p = {\max(e_p, f_p) \text{ if } e_p \ne f_p, \text{ otherwise } 0}$, and let $\lambda_3 = 2^{g_2} 3^{g_3} 5^{g_5} \ldots$. Show that the...
TAOCP 3.2.1.2 Exercise 4
Section 3.2.1.2: Choice of Multiplier Exercise 4. [ M20 ] Assume that $m = 2^e$ and $X_0 = 0$. If the numbers $a$ and $c$ satisfy the conditions of Theorem A, what is the value of $X_{2^{e-1}}$? Verified: yes Solve time: 1m32s Solution We are given a linear congruential sequence $X_{n+1} = (a X_n + c) \bmod 2^e$ with $X_0 = 0$, and where $a$ and $c$ satisfy the conditions...
TAOCP 3.2.1.1 Exercise 13
Section 3.2.1.1: Choice of Modulus Exercise 13. [ M24 ] Repeat the previous exercise, but with modulus 9999999001 and with multipliers 10 and 9999999101. Verified: yes Solve time: 1m54s Solution Let $m=9999999001=10^{10}-999=10^{10}-31^2.$ The congruence $$$$ is the fundamental relation. Every computation modulo $m$ can therefore be reduced by replacing a block of ten decimal digits by $999$ times that block. (a) Multiplication by $10$ modulo $9999999001$ Write $$$$ where $0\le...
TAOCP 3.2.1.1 Exercise 9
Section 3.2.1.1: Choice of Modulus Exercise 9. ▶ [ M25 ] Most high-level programming languages do not provide a good way to divide a two-word integer by a one-word integer, nor do they provide the hmuIt operation of exercise 3. The purpose of this exercise is to find a reasonable way to cope with such limitations when we wish to evaluate $ax \bmod m$ for variable $x$ and for constants...
TAOCP 3.2.1.1 Exercise 7
Section 3.2.1.1: Choice of Modulus Exercise 7. [ M24 ] What patterns can you spot in Table 1? Verified: yes Solve time: 1m48s Solution Examination of Table 1 reveals several recurring structural patterns in the factorizations of $w \pm 1$. First, consider numbers of the form $2^e - 1$. Many of these are Mersenne numbers , and when $e$ is prime, $2^e - 1$ is often prime, as in $2^{17}-1...
TAOCP 3.2.1 Exercise 5
Section 3.2.1: The Linear Congruential Method Exercise 5. [ M20 ] Equation (6) holds for $k \ge 0$. If possible, give a formula that expresses $X_{n+k}$ in terms of $X_n$ for negative values of $k$. Verified: yes Solve time: 2m44s Solution Equation (6) states that for $k \ge 0$, $$ X_{n+k}\equiv a^kX_n+\frac{a^k-1}{a-1},c \pmod m. $$ We seek an analogous formula for negative $k$. The recurrence $$ X_{n+1}\equiv aX_n+c \pmod m...
TAOCP 3.2.1 Exercise 2
Section 3.2.1: The Linear Congruential Method Exercise 2. ▶ [ M20 ] Show that if $a$ and $m$ are relatively prime, the number $X_0$ will always appear in the period. Verified: yes Solve time: 4m21s Solution Let $$ X_{n+1}\equiv aX_n+c \pmod m, $$ and assume that $$ (a,m)=1. $$ We must show that $X_0$ belongs to the periodic part of the sequence, that is, there exists $k>0$ such that $$...
TAOCP 2.3.2 Exercise 12
Section 2.3.2: Binary Tree Representation of Trees Exercise 12. [ M21 ] Give specifications for the routine DIFF[8] (the " ↑ " operation), which was omitted from the algorithm in the text. Verified: yes Solve time: 4m07s Corrected Solution for Exercise 2.3.2.12 We are asked to give specifications for the routine DIFF[8] , which handles differentiation of expressions of the form $u \uparrow v$ (exponentiation) in the context of the...
TAOCP 2.3.2 Exercise 14
Section 2.3.2: Binary Tree Representation of Trees Exercise 14. [ M21 ] How long does it take the program of exercise 13 to copy a tree with n nodes? Verified: yes Solve time: 1m15s Solution Exercise 14 asks for the running time of the COPY subroutine of Exercise 13. The hint for Exercise 13 directs us to adapt Algorithm 2.3.1C to right-threaded binary trees. Therefore the copied tree is traversed...
TAOCP 2.3.3 Exercise 16
Section 2.3.3: Other Representations of Trees Exercise 16. [ M24 ] Prove the validity of Algorithm F . Verified: yes Solve time: 1m36s Solution Let the given forest be represented in postorder with degrees as in representation (9) . For each node $x$, let $\deg(x)$ denote its degree, and let $f(x)$ be the value to be computed. By hypothesis, $f(x)$ depends only on $x$ and on the values of $f$...
TAOCP 2.3.2 Exercise 20
Section 2.3.2: Binary Tree Representation of Trees Exercise 20. [ M22 ] Prove that if u and v are nodes of a forest, u is a proper ancestor of v if and only if u precedes v in preorder and u follows v in postorder. Verified: yes Solve time: 1m22s Solution Let $F$ be a forest and let $u, v$ be nodes in $F$. We aim to prove that $u$...
TAOCP 2.3.1 Exercise 29
Section 2.3.1: Traversing Binary Trees Exercise 29. [ M25 ] Prove as rigorously as possible that Algorithm C is valid. Verified: no Solve time: 53s Solution Algorithm C is intended to construct a new binary tree whose nodes contain the same information as the original tree and whose link structure is identical, regardless of whether a field represents an ordinary subtree link, a left thread, a right thread, or both....
TAOCP 2.3.2 Exercise 9
Section 2.3.2: Binary Tree Representation of Trees Exercise 9. [ M21 ] Show that the total number of nonterminal nodes in a forest has a simple relation to the total number of right links equal to Λ in the corresponding unthreaded binary tree. Verified: yes Solve time: 2m27s Solution Let $F$ be a forest containing $t$ trees. Under the natural correspondence between forests and binary trees, each node of $F$...
TAOCP 2.3.2 Exercise 8
Section 2.3.2: Binary Tree Representation of Trees Exercise 8. [ M20 ] Exercise 2.3.1-25 shows how an ordering between the information stored in the individual nodes of a binary tree may be extended to a linear ordering of all binary trees. The same construction leads to an ordering of all trees, under the natural correspondence. Reformulate the definition of that exercise, in terms of trees. Verified: yes Solve time: 1m20s...
TAOCP 2.3.1 Exercise 6
Section 2.3.1: Traversing Binary Trees Exercise 6. [ M22 ] Suppose that a binary tree has n nodes that are u_1 u_2 ... u_n in preorder and u_{p_1} u_{p_2} ... u_{p_n} in inorder. Show that the permutation p_1 p_2 ... p_n can be obtained by passing 12 ... n through a stack, in the sense of exercise 2.2.1-2 . Conversely, show that any permutation p_1 p_2 ... p_n obtainable with...
TAOCP 2.3.1 Exercise 26
Section 2.3.1: Traversing Binary Trees Exercise 26. [ M24 ] Consider the ordering T \preceq T' defined in the preceding exercise. Prove a theorem analogous to Theorem A , giving a necessary and sufficient condition that T \preceq T' , and making use of double order as defined in exercise 18 . Verified: no Solve time: 59s Solution Let $D(T)$ denote the double-order sequence of a binary tree $T$, as...
TAOCP 2.3.1 Exercise 25
Section 2.3.1: Traversing Binary Trees Exercise 25. [ M24 ] Let \mathcal{T} be a set of binary trees in which the value of each info field belongs to a given set S , where S is linearly ordered by a relation " \preceq " (see exercise 2.2.3-14 ). Given any trees T, T' in \mathcal{T} , let us now define T \preceq T' if and only if T is empty;...
TAOCP 2.3.2 Exercise 10
Section 2.3.2: Binary Tree Representation of Trees Exercise 10. [ M23 ] Let F be a forest of trees whose nodes in preorder are u_1, u_2, ..., u_n , and let F' be a forest whose nodes in preorder are u'_1, u'_2, ..., u'_{n'} . Let d(u) denote the degree (the number of children) of node u . In terms of these ideas, formulate and prove a theorem analogous to...
TAOCP 2.3.1 Exercise 36
Section 2.3.1: Traversing Binary Trees Exercise 36. [ M23 ] Exercise 1.2.1-15 shows that lexicographic order extends a well-ordering of a set S to a well-ordering of the n -tuples of elements of S . Exercise 25 above shows that a linear ordering of the information in tree nodes can be extended to a linear ordering of trees, using a similar definition. If the relation \prec well-orders S , is...
TAOCP 2.3.1 Exercise 24
Section 2.3.1: Traversing Binary Trees Exercise 24. [ M20 ] Is Theorem A still valid if the nodes of T and T' are given in symmetric order instead of preorder? Verified: no Solve time: 46s Solution No. Theorem A depends essentially on the nodes being listed in preorder. In preorder, the root of every subtree appears before all nodes of that subtree, so the sequence contains enough structural information to...
TAOCP 2.3.2 Exercise 7
Section 2.3.2: Binary Tree Representation of Trees Exercise 7. [ M20 ] A forest may be regarded as a partial ordering, if we say that each node precedes its descendants in the tree. Are the nodes topologically sorted (as defined in Section 2.2.3 ) when they are listed in (a) preorder? (b) postorder? (c) reverse preorder? (d) reverse postorder? Verified: yes Solve time: 1m07s Solution Let the partial order on...
TAOCP 2.3.1 Exercise 9
Section 2.3.1: Traversing Binary Trees Exercise 9. [ M20 ] When a binary tree having n nodes is traversed using Algorithm T , state how many times each of steps T1, T2, T3, T4, and T5 is performed (as a function of n ). Verified: no Solve time: 38s Solution Let a binary tree with n nodes be traversed using Algorithm T . We determine the number of times each...
TAOCP 2.2.3 Exercise 16
Section 2.2.3: Linked Allocation Exercise 16. [ M22 ] Given any partial ordering on a set $S = {x_1, \ldots, x_n}$, we can construct its incidence matrix $(a_{ij})$, where $a_{ij} = 1$ if $x_i \preceq x_j$, and $a_{ij} = 0$ otherwise. Show that there is a way to permute the rows and columns of this matrix so that all entries below the diagonal are zero. Verified: yes Solve time: 29s...
TAOCP 2.2.3 Exercise 15
Section 2.2.3: Linked Allocation Exercise 15. [ M25 ] Show that for any partial ordering on a finite set $S$ there is a unique set of irredundant relations that characterizes this ordering, as in (18) and Fig. 6. Is the same fact true also when $S$ is an infinite set? Verified: yes Solve time: 1m49s Solution Let $(S,\preceq)$ be a partially ordered set. Following the terminology of (18) and Fig....
TAOCP 2.2.3 Exercise 12
Section 2.2.3: Linked Allocation Exercise 12. [ M20 ] There are $2^n$ subsets of a set of $n$ elements, and these subsets are partially ordered by the set-inclusion relation. Give two interesting ways to arrange these subsets in topological order. Verified: yes Solve time: 48s Solution Let $S$ be a set of $n$ elements. The family of all subsets of $S$ contains $2^n$ elements and is partially ordered by inclusion....
TAOCP 2.2.3 Exercise 10
Section 2.2.3: Linked Allocation Exercise 10. [ M21 ] Given that "$\subset$" is a relation that satisfies properties (i) and (ii) of a partial ordering, prove that the relation "$\preceq$", defined by the rule "$x \preceq y$ if and only if $x = y$ or $x \subset y$," satisfies all three properties of a partial ordering. Verified: yes Solve time: 35s Solution Assume that the relation "$\subset$" satisfies properties (i)...
TAOCP 2.2.3 Exercise 14
Section 2.2.3: Linked Allocation Exercise 14. [ M21 ] A linear ordering of a set $S$, also called a total ordering , is a partial ordering that satisfies the additional "comparability" condition $$ \text{(iv)} \qquad \text{For any two objects } x,\ y \text{ in } S,\ \text{either } x \preceq y \text{ or } y \preceq x. $$ Prove directly from the definitions given that a topological sort can result...
TAOCP 1.4.4 Exercise 4
Section 1.4.4: Input and Output Exercise 4. [ M20 ] Show that if a program refers to a single I/O device, we might be able to cut the running time in half by buffering the I/O, in favorable circumstances; but we can never decrease the running time by more than a factor of two, with respect to the time taken by unbuffered I/O. Verified: no Solve time: - Solution Let...
TAOCP 2.2.1 Exercise 10
Section 2.2.1: Stacks, Queues, and Deques Exercise 10. [ M25 ] (See exercise 3.) Let S , Q , and X denote respectively the operations of inserting an element at the left, inserting an element at the right, and emitting an element from the left, of an output-restricted deque. For example, the sequence QQXSXSXX will transform the input sequence 1234 into 1342 . The sequence SXQSXSXX gives the same transformation....
TAOCP 1.4.4 Exercise 5
Section 1.4.4: Input and Output Exercise 5. [ M21 ] Generalize the situation of the preceding exercise to the case when the program refers to $n$ I/O devices instead of just one. Verified: no Solve time: - Solution Let $$ T_i $$ be the total time during which I/O device $i$ is actually transferring data, for $1\le i\le n$, and let $$ C $$ be the total computation time exclusive...
TAOCP 2.2.1 Exercise 9
Section 2.2.1: Stacks, Queues, and Deques Exercise 9. [ M20 ] Let $b_n$ be the number of permutations on $n$ elements obtainable by the use of an input-restricted deque. (Note that $b_4 = 22$, as shown in exercise 7.) Show that $b_n$ is also the number of permutations on $n$ elements with an output-restricted deque. Verified: no Solve time: - Solution We denote by $b_n$ the number of permutations on...
TAOCP 1.3.3 Exercise 29
Section 1.3.3: Applications to Permutations Exercise 29. [ M25 ] Prove that the cycle form of the Josephus permutation when $m = 2$ can be obtained by first expressing the "perfect shuffle" permutation of ${1, 2, \ldots, 2n}$, which takes $(1, 2, \ldots, 2n)$ into $(2, 4, \ldots, 2n, 1, 3, \ldots, 2n - 1)$, in cycle form, then reversing left and right and erasing all the numbers greater than...
TAOCP 1.3.3 Exercise 21
Section 1.3.3: Applications to Permutations Exercise 21. [ M22 ] What is the probability $P(n;\alpha_1,\alpha_2,\ldots)$ that a permutation of $n$ objects has exactly $\alpha_1$ one-cycles, $\alpha_2$ two-cycles, etc.? Verified: yes Solve time: 42s Solution Let a permutation of $n$ objects have exactly $\alpha_k$ cycles of length $k$ for each $k \ge 1$, with only finitely many nonzero $\alpha_k$. The constraint on the parameters is $$ \sum_{k \ge 1} k \alpha_k...
TAOCP 1.3.3 Exercise 28
Section 1.3.3: Applications to Permutations Exercise 28. [ M21 ] (I. Kaplansky.) If the "Josephus permutation" defined in exercise 1.3.2-22 is expressed in cycle form, we obtain $(1,5,3,6,8,2,4)(7)$ when $n = 8$ and $m = 4$. Show that this permutation in the general case is the product $(n\ n!-!1\ \ldots\ 2\ 1)^{m-1} \times (n\ n!-!1\ \ldots\ 2)^{m-1}\cdots (n\ n!-!1)^{m-1}$. Verified: no Solve time: 5m35s Solution For $1\le k\le n$, let...
TAOCP 1.3.3 Exercise 20
Section 1.3.3: Applications to Permutations Exercise 20. [ M20 ] Given that all singleton cycles are written out explicitly, how many different ways are there to write the cycle notation of a permutation that has $\alpha_1$ one-cycles, $\alpha_2$ two-cycles, ... ? (See exercise 5.) Verified: yes Solve time: 2m07s Solution Let $$ r=\alpha_1+\alpha_2+\alpha_3+\cdots $$ be the total number of cycles of the permutation, including the one-cycles. Two independent choices determine...
TAOCP 1.3.3 Exercise 13
Section 1.3.3: Applications to Permutations Exercise 13. [ M24 ] Prove that Algorithm $J$ is valid. Verified: yes Solve time: 9m43s Let the current permutation be $$ P = (a_1,a_2,\dots,a_n). $$ Algorithm $J$ constructs a new permutation $Q$ as follows: Choose the largest index $i$ such that $a_i < a_{i+1}$. Choose the largest index $j>i$ such that $a_j > a_i$. Swap $a_i$ and $a_j$. Reverse the suffix $a_{i+1},\dots,a_n$. We prove...
TAOCP 1.3.3 Exercise 26
Section 1.3.3: Applications to Permutations Exercise 26. [ M24 ] Extend the principle of inclusion and exclusion to obtain a formula for the number of elements that are in exactly $r$ of the subsets $S_1, S_2, \ldots, S_M$. (The text considers only the case $r = 0$.) Verified: yes Solve time: 26m57s Solution Let $S_1, S_2, \ldots, S_M$ be subsets of a fixed universe $U$. For each element $x \in...
TAOCP 1.3.3 Exercise 30
Section 1.3.3: Applications to Permutations Exercise 30. [ M24 ] Use exercise 29 to show that the fixed elements of the Josephus permutation when $m = 2$ are precisely the numbers $(2^d - 1)(2n + 1)/(2^{d+1} - 1)$ for all positive integers $d$ such that this is an integer. Verified: yes Solve time: 8m56s Corrected Solution Let $n$ be a positive integer, and let $J_{2n+1}$ denote the Josephus permutation for...
TAOCP 1.3.3 Exercise 34
Section 1.3.3: Applications to Permutations Exercise 34. [ M25 ] ( Transposing blocks of data. ) One of the most common permutations needed in practice is the change from $\alpha\beta$ to $\beta\alpha$, where $\alpha$ and $\beta$ are substrings of an array. In other words, if $x_0x_1\ldots x_{m-1} = \alpha$ and $x_mx_{m+1}\ldots x_{m+n-1} = \beta$, we want to change the array $x_0x_1\ldots x_{m+n-1} = \alpha\beta$ to the array $x_mx_{m+1}\ldots x_{m+n-1}x_0x_1\ldots x_{m-1}...
TAOCP 1.3.3 Exercise 25
Section 1.3.3: Applications to Permutations Exercise 25. [ M22 ] Prove Eq. (29). Verified: yes Solve time: 27m26s Solution Let $S_n$ be the set of all permutations of ${1,2,\dots,n}$, each taken with equal probability $1/n!$. Let $X(\pi)$ denote the number of cycles in a permutation $\pi \in S_n$. Equation (29) asserts that the mean value satisfies $$ \mathbb{E}[X] = 1 + \frac{1}{2} + \cdots + \frac{1}{n}. $$ For $i \in...
TAOCP 1.3.3 Exercise 32
Section 1.3.3: Applications to Permutations Exercise 32. [ M25 ] (a) Prove that any permutation $\pi = \pi_1\pi_2\cdots\pi_{2m+1}$ of the form $$ \pi = (2,3)^{e_2}(4,5)^{e_4}\cdots(2m\ 2m!+!1)^{e_{2m}}(1,2)^{e_1}(3,4)^{e_3}\cdots(2m!-!1\ 2m)^{e_{2m-1}}, $$ where each $e_k$ is $0$ or $1$, has $|\pi_k - k| \le 2$ for $1 \le k \le 2m + 1$. (b) Given any permutation $\rho$ of ${1, 2, \ldots, n}$, construct a permutation $\pi$ of the stated form such that $\rho\pi$...
TAOCP 1.3.3 Exercise 17
Section 1.3.3: Applications to Permutations Exercise 17. [ M24 ] (a) The text demonstrates that there are $n!H_n$ cycles altogether, among all the permutations on $n$ elements. If these cycles (including singleton cycles) are individually written on $n!H_n$ slips of paper, and if one of these slips of paper is chosen at random, what is the average length of the cycle that is thereby picked? (b) If we write the...
TAOCP 1.3.3 Exercise 27
Section 1.3.3: Applications to Permutations Exercise 27. [ M20 ] Use the principle of inclusion and exclusion to count the number of integers $n$ in the range $0 \le n < am_1m_2\cdots m_t$ that are not divisible by any of $m_1, m_2, \ldots, m_t$. Here $m_1, m_2, \ldots, m_t$, and $a$ are positive integers, with $m_j \perp m_k$ when $j \ne k$. Verified: yes Solve time: 42s Solution Let $$...
TAOCP 1.2.9 Exercise 20
Section 1.2.9: Generating Functions Exercise 20. [ M21 ] For what coefficients $c_{mk}$ is $$ \sum_{n \ge 0} n^m z^n = \sum_{k=0}^{m} c_{mk}\frac{z^k}{(1-z)^{k+1}} , ? $$ Verified: yes Solve time: 1m Solution We are asked to express the generating function $$ \sum_{n \ge 0} n^m z^n $$ in the form $$ \sum_{k=0}^{m} c_{mk}\frac{z^k}{(1-z)^{k+1}}. $$ Let $G_m(z) = \sum_{n \ge 0} n^m z^n$. By Eq. (5), we have $$ \sum_{n \ge...
TAOCP 1.2.9 Exercise 22
Section 1.2.9: Generating Functions Exercise 22. [ M21 ] Find a generating function $G(z)$ for which $$ [z^n]G(z) = \sum_{k_0+2k_1+4k_2+8k_3+\cdots=n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\binom{r}{k_3}\cdots . $$ Verified: yes Solve time: 1m05s Solution We are asked to find a generating function $G(z)$ such that the coefficient of $z^n$ is $$ [z^n]G(z) = \sum_{k_0+2k_1+4k_2+8k_3+\cdots=n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\binom{r}{k_3}\cdots. $$ Observe that the sum runs over all sequences of nonnegative integers $(k_0,k_1,k_2,\ldots)$ such that $$ \sum_{j \ge 0} 2^j...
TAOCP 1.2.9 Exercise 18
Section 1.2.9: Generating Functions Exercise 18. [ M25 ] Given positive integers $n$ and $r$, find a simple formula for the value of the following sums: (a) $\sum_{1 \le k_1 < k_2 < \cdots < k_r \le n} k_1k_2\cdots k_r$; (b) $\sum_{1 \le k_1 \le k_2 \le \cdots \le k_r \le n} k_1k_2\cdots k_r$. (For example, when $n=3$ and $r=2$ the sums are, respectively, $1\cdot2 + 1\cdot3 + 2\cdot3$ and...
TAOCP 1.2.9 Exercise 25
Section 1.2.9: Generating Functions Exercise 25. [ M23 ] Evaluate the sum $$ \sum_k \binom{n}{k} 2^{n-2k}(-2)^k $$ by simplifying the equivalent formula $$ \sum_k w^k ^n z^{n-k} ^{2n-2k}. $$ Verified: no Solve time: 4m29s Solution Let $$ S=\sum_k w^k ^n, z^{,n-k} ^{2n-2k}. $$ We simplify this coefficient-extraction formula directly. First observe that $$ z^{,n-k} ^{2n-2k} = z^{,n-k} ^{2(n-k)} =\binom{2(n-k)}{,n-k,}. $$ Hence $$ S=\sum_k \binom{n}{k}(-2)^k \binom{2(n-k)}{,n-k,}, $$ since $$ w^k ^n=\binom{n}{k}(-2)^k....
TAOCP 1.2.9 Exercise 24
Section 1.2.9: Generating Functions Exercise 24. [ M22 ] Prove that, if $G(z)$ is any generating function, we have $$ \sum_k \binom{m}{k}[z^{,n-k}]G(z)^k = z^n ^m. $$ Evaluate both sides of this identity when $G(z)$ is (a) $1/(1-z)$; (b) $(e^z-1)/z$. Verified: yes Solve time: 54s Solution We start from the right-hand side and extract the coefficient of $z^n$. $$ (1+zG(z))^m = \sum_{k=0}^m \binom{m}{k} (zG(z))^k = \sum_{k=0}^m \binom{m}{k} z^k G(z)^k. $$ For...
TAOCP 1.2.8 Exercise 25
Section 1.2.8: Fibonacci Numbers Exercise 25. [ M21 ] Show that $$ 2^nF_n = 2 \sum_{k\ \mathrm{odd}} \binom{n}{k} 5^{(k-1)/2}. $$ Verified: no Solve time: - Solution By Eq. (14), $$ F_n=\frac{1}{\sqrt5}(\phi^n-\hat\phi^n), $$ where $$ \phi=\frac{1+\sqrt5}{2}, \qquad \hat\phi=\frac{1-\sqrt5}{2}. $$ Hence $$ 2^nF_n = \frac{1}{\sqrt5}\bigl((2\phi)^n-(2\hat\phi)^n\bigr). $$ Since $$ 2\phi=1+\sqrt5, \qquad 2\hat\phi=1-\sqrt5, $$ we obtain $$ 2^nF_n = \frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{\sqrt5}. $$ Applying the binomial theorem gives $$ (1+\sqrt5)^n = \sum_{k=0}^n \binom{n}{k}(\sqrt5)^k, $$ and $$...
TAOCP 1.2.8 Exercise 28
Section 1.2.8: Fibonacci Numbers Exercise 28. [ M21 ] What is $F_{n+1}-\phi F_n$? Verified: no Solve time: - Solution From the closed form expression (14) for the Fibonacci numbers, we have $$ F_n = \frac{1}{\sqrt{5}}\bigl(\phi^n - \hat{\phi}^n\bigr), \qquad \hat{\phi} = 1-\phi = \frac{1}{2}(1-\sqrt{5}). $$ We want to compute $F_{n+1} - \phi F_n$. Substituting the closed forms gives $$ \begin{aligned} F_{n+1} - \phi F_n &= \frac{1}{\sqrt{5}}\bigl(\phi^{n+1} - \hat{\phi}^{,n+1}\bigr) - \phi \cdot...
TAOCP 1.2.9 Exercise 17
Section 1.2.9: Generating Functions Exercise 17. [ M25 ] What are the coefficients of $1/(1-z)^w$ if this function is expanded into a double power series in terms of both $z$ and $w$? Verified: yes Solve time: 50s Solution We seek the coefficients of $$ \frac{1}{(1-z)^w} $$ when expanded as a double power series in $z$ and $w$. By the binomial theorem for general exponents (see Eq. (19)), we have $$...
TAOCP 1.2.8 Exercise 35
Section 1.2.8: Fibonacci Numbers Exercise 35. [ M24 ] ( A phi number system. ) Consider real numbers written with the digits $0$ and $1$ using base $\phi$; thus $(100.1)_\phi = \phi^2 + \phi^{-1}$. Show that there are infinitely many ways to represent the number $1$; for example, $$ 1 = (.11) \phi = (.011111\ldots) \phi. $$ But if we require that no two adjacent 1s occur and that the...
TAOCP 1.2.9 Exercise 11
Section 1.2.9: Generating Functions Exercise 11. [ M25 ] Equation (39) can also be used to express the $S$'s in terms of the $h$'s: We find $S_1=h_1$, $S_2=2h_2-h_1^2$, $S_3=3h_3-3h_1h_2+h_1^3$, etc. What is the coefficient of $h_1^{k_1}h_2^{k_2}\cdots h_m^{k_m}$ in this representation of $S_m$, when $k_1+2k_2+\cdots+mk_m=m$? Verified: yes Solve time: 7m Solution Let H(z)=\sum_{m\ge0}h_m z^m ] be the generating function for the complete homogeneous symmetric functions. By equation (39), \ln H(z)=\sum_{j\ge1}\frac{S_j}{j}z^j. \tag{1}...
TAOCP 1.2.8 Exercise 17
Section 1.2.8: Fibonacci Numbers Exercise 17. [ M24 ] Using the conventions of exercise 8, prove the following generalization of Eq. (4): $$ F_{n+k}F_{m-k} - F_nF_m = (-1)^n F_{m-n-k}F_k. $$ Verified: yes Solve time: 44s Solution Using the conventions of exercise 8, Fibonacci numbers are extended to all integer subscripts. In particular, $$ F_{-r}=(-1)^{r+1}F_r . $$ Apply Eq. (6) with $m=k$ and $n$ replaced by $n$: $$ F_{n+k}=F_kF_{n+1}+F_{k-1}F_n. $$ Similarly,...
TAOCP 1.2.8 Exercise 34
Section 1.2.8: Fibonacci Numbers Exercise 34. [ M24 ] ( The Fibonacci number system. ) Let the notation $k \gg m$ mean that $k \ge m+2$. Show that every positive integer $n$ has a unique representation $$ n = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, $$ where $k_1 \gg k_2 \gg \cdots \gg k_r \gg 0$. Verified: no Solve time: - Solution We prove existence and uniqueness separately. Define...
TAOCP 1.2.8 Exercise 23
Section 1.2.8: Fibonacci Numbers Exercise 23. [ M23 ] Generalizing the preceding exercise, show that $$ \sum_k \binom{n}{k} F_t^k F_{t-1}^{,n-k} F_{m+k} $$ is always a Fibonacci number. Verified: yes Solve time: 2m21s We restart from a clean derivation and fix the missing structural step directly. Correct solution Let $$ S=\sum_{k=0}^{n}\binom{n}{k}F_t^k F_{t-1}^{,n-k}F_{m+k}. $$ We use Binet’s formula $$ F_r=\frac{\phi^r-\hat\phi^r}{\sqrt{5}}, \quad \text{where } \phi=\frac{1+\sqrt5}{2},\ \hat\phi=\frac{1-\sqrt5}{2}. $$ Substitute this into $S$: $$ S=\sum_{k=0}^{n}\binom{n}{k}F_t^k...
TAOCP 1.2.8 Exercise 20
Section 1.2.8: Fibonacci Numbers Exercise 20. [ M16 ] Express $\sum_{k=0}^{n} F_k$ in terms of Fibonacci numbers. Verified: no Solve time: - Solution We wish to find a closed form for $$ S_n = \sum_{k=0}^{n} F_k $$ in terms of Fibonacci numbers. We proceed by using the Fibonacci recurrence $$ F_{k+2} = F_{k+1} + F_k \quad \text{for } k \ge 0. $$ Consider the sum of the first $n+2$ Fibonacci...
TAOCP 1.2.8 Exercise 27
Section 1.2.8: Fibonacci Numbers Exercise 27. [ M20 ] Using the previous exercise, show that if $p$ is a prime different from $5$, then either $F_{p-1}$ or $F_{p+1}$ (not both) is a multiple of $p$. Verified: no Solve time: - Solution Let $p$ be a prime with $p \ne 5$. By Exercise 1.2.8.26, we have $$ F_p \equiv 5^{(p-1)/2} \pmod p. $$ By Euler's criterion, since $p \ne 5$, $$...
TAOCP 1.2.9 Exercise 12
Section 1.2.9: Generating Functions Exercise 12. [ M20 ] Suppose we have a doubly subscripted sequence $\langle a_{mn} \rangle$ for $m,n=0,1,\ldots$; show how this double sequence can be represented by a single generating function of two variables, and determine the generating function for $\left\langle \binom{n}{m} \right\rangle$. Verified: yes Solve time: 6m41s Solution A doubly subscripted sequence $\langle a_{mn} \rangle$ with $m,n \ge 0$ is represented by introducing two independent parameters...
TAOCP 1.2.8 Exercise 41
Section 1.2.8: Fibonacci Numbers Exercise 41. [ M25 ] (Yuri Matiyasevich, 1990.) Let $f(x)=\lfloor x+\phi^{-1}\rfloor$. Prove that if $$ n = F_{k_1} + \cdots + F_{k_r} $$ is the representation of $n$ in the Fibonacci number system of exercise 34, then $$ F_{k_1+1} + \cdots + F_{k_r+1} = f(\phi n). $$ Find a similar formula for $F_{k_1-1} + \cdots + F_{k_r-1}$. Verified: yes Solve time: 10m24s Solution Let $$ n...
TAOCP 1.2.8 Exercise 21
Section 1.2.8: Fibonacci Numbers Exercise 21. [ M25 ] What is $\sum_{k=0}^{n} F_kx^k$? Verified: no Solve time: - Solution Let $$ S_n(x)=\sum_{k=0}^{n}F_kx^k. $$ We seek a closed form for $S_n(x)$. By the defining recurrence, $$ F_k=F_{k-1}+F_{k-2} \qquad (k\ge2), $$ hence $$ S_n(x) =F_0+F_1x+\sum_{k=2}^{n}(F_{k-1}+F_{k-2})x^k. $$ Since $F_0=0$ and $F_1=1$, $$ S_n(x) =x+\sum_{k=2}^{n}F_{k-1}x^k+\sum_{k=2}^{n}F_{k-2}x^k. $$ Rewrite the sums: $$ \sum_{k=2}^{n}F_{k-1}x^k =x\sum_{k=2}^{n}F_{k-1}x^{k-1} =x\sum_{j=1}^{n-1}F_jx^j =xS_n(x)-F_nx^{n+1}, $$ and $$ \sum_{k=2}^{n}F_{k-2}x^k =x^2\sum_{k=2}^{n}F_{k-2}x^{k-2} =x^2\sum_{j=0}^{n-2}F_jx^j =x^2S_n(x)-F_{n-1}x^{n+1}-F_nx^{n+2}. $$ Therefore $$...
TAOCP 1.2.8 Exercise 29
Section 1.2.8: Fibonacci Numbers Exercise 29. [ M23 ] ( Fibonomial coefficients. ) Edouard Lucas defined the quantities $$ \binom{n}{k} {\mathcal{F}} = \frac{F_nF {n-1}\cdots F_{n-k+1}}{F_kF_{k-1}\cdots F_1} = \prod_{j=1}^{k}\left(\frac{F_{n-k+j}}{F_j}\right) $$ in a manner analogous to binomial coefficients. (a) Make a table of $\binom{n}{k} {\mathcal{F}}$ for $0 \le k \le n \le 6$. (b) Show that $\binom{n}{k} {\mathcal{F}}$ is always an integer because we have $$ \binom{n}{k} {\mathcal{F}} = F {k-1}\binom{n-1}{k}_{\mathcal{F}} F_{n-k+1}\binom{n-1}{k-1}_{\mathcal{F}}....
TAOCP 1.2.8 Exercise 32
Section 1.2.8: Fibonacci Numbers Exercise 32. [ M24 ] The remainder of one Fibonacci number divided by another is $\pm$ a Fibonacci number: Show that, modulo $F_n$, $$ F_{mn+r} \equiv \begin{cases} F_r, & \text{if } m \bmod 4 = 0; \ (-1)^{r+1}F_{n-r}, & \text{if } m \bmod 4 = 1; \ (-1)^nF_r, & \text{if } m \bmod 4 = 2; \ (-1)^{r+1+n}F_{n-r}, & \text{if } m \bmod 4 = 3....
TAOCP 1.2.9 Exercise 16
Section 1.2.9: Generating Functions Exercise 16. [ M22 ] Give a simple formula for the generating function $$ G_n^{(r)}(z) = \sum_k a_{nkr} z^k, $$ where $a_{nkr}$ is the number of ways to choose $k$ out of $n$ objects, subject to the condition that each object may be chosen at most $r$ times. (If $r=1$, we have $\binom{n}{k}$ ways, and if $r \ge k$, we have the number of combinations with...
TAOCP 1.2.9 Exercise 5
Section 1.2.9: Generating Functions Exercise 5. [ M20 ] Prove Eq. (23) by induction on $n$. Verified: no Solve time: - Solution For fixed $n$, define $$ F_n(z) = (e^z-1)^n. $$ We must prove that $$ F_n(z) = n!\sum_{k \ge 0} \left{ {k \atop n} \right}\frac{z^k}{k!}. \tag{23} $$ The proof proceeds by induction on $n$. When $n=0$, $$ F_0(z)=1. $$ Since $$ \left{ {0 \atop 0} \right}=1, \qquad \left{ {k...
TAOCP 1.2.8 Exercise 40
Section 1.2.8: Fibonacci Numbers Exercise 40. [ M25 ] Solve the recurrence $$ f(1)=0; \qquad f(n)=\min_{0<k<n}\max(1+f(k),,2+f(n-k)), \qquad n>1. $$ Verified: no Solve time: - Solution We are asked to solve the recurrence $$ f(1)=0; \qquad f(n)=\min_{0<k<n}\max(1+f(k),,2+f(n-k)), \qquad n>1. $$ We proceed by analyzing the structure of the recurrence. Step 1: Understand the recurrence. For $n>1$, $f(n)$ is the minimum over $k=1,2,\dots,n-1$ of $\max(1+f(k),2+f(n-k))$. This can be interpreted as a two-stage...
TAOCP 1.2.8 Exercise 11
Section 1.2.8: Fibonacci Numbers Exercise 11. [ M20 ] Show that $\phi^n = F_n\phi + F_{n-1}$ and $\hat{\phi}^n = F_n\hat{\phi} + F_{n-1}$, for all integers $n$. Verified: yes Solve time: 42s Solution We prove the identities $$ \phi^n = F_n \phi + F_{n-1}, \qquad \hat{\phi}^n = F_n \hat{\phi} + F_{n-1} $$ for all integers $n$ by induction and by using the definitions in Section 1.2.8. Step 1: Base cases. For...
TAOCP 1.2.8 Exercise 13
Section 1.2.8: Fibonacci Numbers Exercise 13. [ M22 ] Express the following sequences in terms of the Fibonacci numbers, when $r$, $s$, and $c$ are given constants: a) $a_0=r$, $a_1=s$; $a_{n+2}=a_{n+1}+a_n$, for $n \ge 0$. b) $b_0=0$, $b_1=1$; $b_{n+2}=b_{n+1}+b_n+c$, for $n \ge 0$. Verified: no Solve time: - Solution (a) Let $$ A(z)=\sum_{n\ge0} a_n z^n $$ be the generating function for the sequence $\langle a_n\rangle$. From the recurrence relation, $$...
TAOCP 1.2.9 Exercise 10
Section 1.2.9: Generating Functions Exercise 10. [ M25 ] An elementary symmetric function is defined by the formula $$ e_m = \sum_{1 \le j_1 < \cdots < j_m \le n} x_{j_1}\cdots x_{j_m}. $$ (This is the same as $h_m$ of Eq. (33), except that equal subscripts are not allowed.) Find the generating function for $e_m$, and express $e_m$ in terms of the $S_j$ in Eq. (34). Write out the formulas...
TAOCP 1.2.8 Exercise 15
Section 1.2.8: Fibonacci Numbers Exercise 15. [ M22 ] Let $f(n)$ and $g(n)$ be arbitrary functions, and for $n \ge 0$ let $$ \begin{aligned} a_0&=0, & a_1&=1, & a_{n+2}&=a_{n+1}+a_n+f(n);\ b_0&=0, & b_1&=1, & b_{n+2}&=b_{n+1}+b_n+g(n);\ c_0&=0, & c_1&=1, & c_{n+2}&=c_{n+1}+c_n+xf(n)+yg(n). \end{aligned} $$ Express $c_n$ in terms of $x$, $y$, $a_n$, $b_n$, and $F_n$. Verified: no Solve time: - Solution Define $$ d_n=c_n-xa_n-yb_n. $$ Since $$ a_0=b_0=c_0=0,\qquad a_1=b_1=c_1=1, $$ we have $$...
TAOCP 1.2.8 Exercise 16
Section 1.2.8: Fibonacci Numbers Exercise 16. [ M20 ] Fibonacci numbers appear implicitly in Pascal's triangle if it is viewed from the right angle. Show that the following sum of binomial coefficients is a Fibonacci number: $$ \sum_{k=0}^{n} \binom{n-k}{k}. $$ Verified: yes Solve time: 43s Solution We want to prove that $$ \sum_{k=0}^{n} \binom{n-k}{k} = F_{n+1}. $$ Define $$ S_n = \sum_{k=0}^{n} \binom{n-k}{k}. $$ We first determine a recurrence for...
TAOCP 1.2.8 Exercise 22
Section 1.2.8: Fibonacci Numbers Exercise 22. [ M20 ] Show that $\sum_k \binom{n}{k}F_{m+k}$ is a Fibonacci number. Verified: no Solve time: - Solution We wish to show that $$ \sum_{k=0}^{n} \binom{n}{k} F_{m+k} $$ is a Fibonacci number. To do so, we will prove that this sum satisfies the Fibonacci recurrence and identify its initial values. Let $$ S_n = \sum_{k=0}^{n} \binom{n}{k} F_{m+k}. $$ We proceed by induction on $n$ using...
TAOCP 1.2.8 Exercise 39
Section 1.2.8: Fibonacci Numbers Exercise 39. [ M24 ] Find a closed form expression for $a_n$, given that $a_0=0$, $a_1=1$, and $a_{n+2}=a_{n+1}+6a_n$ for $n \ge 0$. Verified: no Solve time: - Solution The recurrence relation is $$ a_{n+2}=a_{n+1}+6a_n, $$ with initial conditions $$ a_0=0,\qquad a_1=1. $$ We solve this recurrence by the standard method used to derive Eq. (14). Assume a solution of the form $$ a_n=r^n. $$ Substitution into...
TAOCP 1.2.8 Exercise 26
Section 1.2.8: Fibonacci Numbers Exercise 26. [ M20 ] Using the previous exercise, show that $F_p \equiv 5^{(p-1)/2}$ (modulo $p$) if $p$ is an odd prime. Verified: no Solve time: - Solution We start from Exercise 25, which asserts that $$ 2^n F_n = 2 \sum_{\substack{k=1\ k \text{ odd}}}^{,n} \binom{n}{k} 5^{(k-1)/2}. \tag{25} $$ Let $p$ be an odd prime. We aim to show that $$ F_p \equiv 5^{(p-1)/2} \pmod p....
TAOCP 1.2.8 Exercise 31
Section 1.2.8: Fibonacci Numbers Exercise 31. [ M20 ] Show that $F_{2n}\phi \bmod 1 = 1-\phi^{-2n}$ and $F_{2n+1}\phi \bmod 1 = \phi^{-2n-1}$. Verified: no Solve time: - Solution We are asked to compute $F_n \phi \bmod 1$, that is, the fractional part of $F_n \phi$. By definition, for any real number $x$, $x \bmod 1 = x - \lfloor x \rfloor$. From equation (14) in Section 1.2.8, we have the...
TAOCP 1.2.9 Exercise 8
Section 1.2.9: Generating Functions Exercise 8. [ M23 ] Find the generating function for $p(n)$, the number of partitions of $n$. Verified: yes Solve time: 4m23s Solution Let $p(n)$ denote the number of partitions of $n$, with $p(0)=1$. For each integer $k \ge 1$, the geometric series (5) with $z$ replaced by $z^k$ gives $$ \frac{1}{1-z^k} = 1 + z^k + z^{2k} + \cdots = \sum_{j \ge 0} z^{kj}. $$...
TAOCP 1.2.6 Exercise 61
Section 1.2.6: Binomial Coefficients Exercise 61. [ M25 ] Evaluate the sum $$ \sum_k \left[{n+1 \atop k+1}\right]\left{{k \atop m}\right}(-1)^{k-m}, $$ thereby obtaining a companion formula for Eq. (55). Verified: no Solve time: - Solution Let $$ S=\sum_k \left[{n+1 \atop k+1}\right]\left{{k \atop m}\right}(-1)^{k-m}. $$ We seek a closed form for $S$. The Stirling numbers of the first kind and second kind satisfy the inverse relations of Eq. (55): $$ x^{\underline{n}} =...
TAOCP 1.2.7 Exercise 10
Section 1.2.7: Harmonic Numbers Exercise 10. [ M20 ] (Summation by parts.) Prove the general formula $$ \sum_{1 \le k < n}(a_{k+1}-a_k)b_k = a_nb_n - a_1b_1 - \sum_{1 \le k < n}a_{k+1}(b_{k+1}-b_k). $$ Verified: no Solve time: - Solution Let $$ S=\sum_{1 \le k < n}(a_{k+1}-a_k)b_k. $$ Expand the sum: $$ S = (a_2-a_1)b_1+(a_3-a_2)b_2+\cdots+(a_n-a_{n-1})b_{n-1}. $$ Distribute each factor: $$ S = a_2b_1-a_1b_1+a_3b_2-a_2b_2+\cdots+a_nb_{n-1}-a_{n-1}b_{n-1}. $$ Group terms according to the coefficients of...
TAOCP 1.2.7 Exercise 9
Section 1.2.7: Harmonic Numbers Exercise 9. [ M18 ] Theorem A applies only when $x>0$; what is the value of the sum considered when $x=-1$? Verified: no Solve time: - Solution We are asked to evaluate $$ \sum_{k=1}^{n} \binom{n}{k}(-1)^k H_k. $$ Let $$ S_n = \sum_{k=1}^{n} \binom{n}{k} (-1)^k H_k. $$ We begin by observing that $$ (1 + (-1))^n = 0^n. $$ Hence, for $n \ge 1$, $$ \sum_{k=0}^{n} \binom{n}{k}...
TAOCP 1.2.6 Exercise 55
Section 1.2.6: Binomial Coefficients Exercise 55. [ M21 ] Considering each of Stirling's triangles as matrices, determine their inverses. Verified: yes Solve time: 1m33s Solution Let $$ P=\bigl(\binom{n}{k}\bigr)_{n,k\ge 0} $$ be Pascal's triangle regarded as an infinite lower-triangular matrix. Exercise 54 asks for the inverse of $P$, namely $$ P^{-1}=\bigl((-1)^{,n-k}\binom{n}{k}\bigr)_{n,k\ge0}. \tag{1} $$ The two Stirling triangles are the matrices $$ S=\bigl[{n\atop k}\bigr] {n,k\ge0}, \qquad s=\bigl[{n\atop k}\bigr] {!!*,,n,k\ge0}, $$ where $\bigl[{n\atop...
TAOCP 1.2.6 Exercise 54
Section 1.2.6: Binomial Coefficients Exercise 54. [ M21 ] Consider Pascal's triangle as a matrix. What is the inverse of that matrix? Verified: no Solve time: - Solution Let $P$ denote the infinite lower-triangular matrix whose $(i,j)$ entry is $$ P_{i,j} = \binom{i}{j}, \qquad i,j \ge 0, $$ with the convention that $\binom{i}{j} = 0$ when $j > i$. This is the matrix form of Pascal's triangle. Our goal is...
TAOCP 1.2.7 Exercise 7
Section 1.2.7: Harmonic Numbers Exercise 7. [ M21 ] Let $T(m,n)=H_m+H_n-H_{mn}$. Show that when $m$ or $n$ increases, $T(m,n)$ never increases (assuming that $m$ and $n$ are positive). Compute the minimum and maximum values of $T(m,n)$ for $m,n>0$. Verified: no Solve time: - Solution Let $$ T(m,n) = H_m + H_n - H_{mn}, $$ where $m,n > 0$ and $H_k = \sum_{i=1}^{k} \frac{1}{i}$ is the $k$-th harmonic number. We first...
TAOCP 1.2.6 Exercise 58
Section 1.2.6: Binomial Coefficients Exercise 58. [ M23 ] In the notation of Eq. (40), prove the $q$-nomial theorem: $$ (1+x)(1+qx)\cdots(1+q^{n-1}x) = \sum_k \binom{n}{k}_q q^{k(k-1)/2}x^k. $$ Verified: no Solve time: - Solution We proceed by induction on $n$. Define $f_n(x) = (1+x)(1+qx)\cdots(1+q^{n-1}x).$ The base case is $n=0$. Then $f_0(x) = 1$, and the right-hand side reduces to $\sum_k \binom{0}{k}_q q^{k(k-1)/2} x^k = \binom{0}{0}_q q^{0} x^0 = 1$, as required. Assume...
TAOCP 1.2.7 Exercise 21
Section 1.2.7: Harmonic Numbers Exercise 21. [ M24 ] Evaluate $\sum_{k=1}^{n} H_k/(n+1-k)$. Verified: no Solve time: - Solution Let $$ S_n=\sum_{k=1}^{n}\frac{H_k}{n+1-k}. $$ Replace the index $k$ by $n+1-k$. Then $$ S_n=\sum_{k=1}^{n}\frac{H_{n+1-k}}{k}. $$ Since $$ H_{n+1-k}=H_n-\sum_{j=n+2-k}^{n}\frac1j, $$ we obtain $$ S_n =\sum_{k=1}^{n}\frac{H_n}{k} -\sum_{k=1}^{n}\frac1k\sum_{j=n+2-k}^{n}\frac1j. $$ The first sum equals $$ H_n\sum_{k=1}^{n}\frac1k=H_n^2. $$ For the double sum, write $j=n+1-r$. Then $1\le r\le k-1$, hence $$ \sum_{k=1}^{n}\frac1k\sum_{j=n+2-k}^{n}\frac1j = \sum_{k=1}^{n}\frac1k\sum_{r=1}^{k-1}\frac1{n+1-r}. $$ Interchanging the order of...
TAOCP 1.2.6 Exercise 67
Section 1.2.6: Binomial Coefficients Exercise 67. [ M20 ] Prove the upper bound $$ \binom{n}{k} \le \left(\frac{ne}{k}\right)^k, \qquad n \ge k \ge 0. $$ Verified: no Solve time: - Solution We begin with the definition of the binomial coefficient for integers $n \ge k \ge 0$: $$ \binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1} = \frac{n!}{k!(n-k)!}. \tag{5} $$ Consider the product representation $$ \binom{n}{k} = \frac{n}{1} \cdot \frac{n-1}{2} \cdot \frac{n-2}{3} \cdots \frac{n-k+1}{k} =...
TAOCP 1.2.6 Exercise 60
Section 1.2.6: Binomial Coefficients Exercise 60. [ M23 ] How many $k$-combinations of $n$ objects are there, if repetition is allowed? Verified: no Solve time: - Solution Let the $n$ objects be labeled $1,2,\ldots,n$. A $k$-combination with repetition allowed is equivalent to a sequence $$ x_1,x_2,\ldots,x_k $$ such that $$ 1 \le x_1 \le x_2 \le \cdots \le x_k \le n. $$ For example, when $n=5$ and $k=3$, the combination...
TAOCP 1.2.6 Exercise 64
Section 1.2.6: Binomial Coefficients Exercise 64. [ M20 ] Show that $\left{{n \atop m}\right}$ is the number of ways to partition a set of $n$ elements into $m$ nonempty disjoint subsets. Verified: no Solve time: - Solution Let $S(n,m)$ denote the number of partitions of an $n$-element set into $m$ nonempty disjoint subsets. We will prove that $$ S(n,m)=\left{{n \atop m}\right}, $$ where $\left{{n \atop m}\right}$ denotes the Stirling number...
TAOCP 1.2.7 Exercise 11
Section 1.2.7: Harmonic Numbers Exercise 11. [ M21 ] Using summation by parts, evaluate $$ \sum_{1<k \le n}\frac{1}{k(k-1)}H_k. $$ Verified: yes Solve time: 1m14s Solution Let $$ S=\sum_{1<k\le n}\frac{1}{k(k-1)}H_k. $$ To apply summation by parts in the form of Exercise 10, choose $$ a_k=-\frac1{k-1}\qquad (k\ge2), $$ so that $$ a_{k+1}-a_k =-\frac1k+\frac1{k-1} =\frac1{k(k-1)}. $$ Also take $$ b_k=H_k. $$ Then $$ S=\sum_{1<k\le n}(a_{k+1}-a_k)b_k =\sum_{2\le k\le n}(a_{k+1}-a_k)b_k. $$ Applying the summation-by-parts formula...
TAOCP 1.2.6 Exercise 53
Section 1.2.6: Binomial Coefficients Exercise 53. [ M25 ] Prove by induction on $m$ that $$ \sum_{k=0}^{m}\binom{r}{k}\binom{s}{n-k}\left(nr-(r+s)k\right) = (m+1)(n-m)\binom{r}{m+1}\binom{s}{n-m}. $$ Then use related formulas to derive $$ \sum_{k=0}^{m}\binom{2k-1}{k}\binom{2n-2k}{n-k}\frac{-1}{2k-1} = \frac{n-m}{2n}\binom{2m}{m}\binom{2n-2m}{n-m} \frac{1}{2}\binom{2n}{n}. $$ Verified: yes Solve time: 2m03s Solution Define $$ S_m=\sum_{k=0}^{m}\binom{r}{k}\binom{s}{n-k}\bigl(nr-(r+s)k\bigr). $$ We prove by induction on $m$ that $$ S_m=(m+1)(n-m)\binom{r}{m+1}\binom{s}{n-m}. \tag{1} $$ Induction on $m$ For $m=0$, $$ S_0=\binom{r}{0}\binom{s}{n}(nr)=nr\binom{s}{n}, $$ while the right-hand side of (1) is $$ (0+1)(n-0)\binom{r}{1}\binom{s}{n}...
TAOCP 1.2.7 Exercise 25
Section 1.2.7: Harmonic Numbers Exercise 25. [ M21 ] Let $$ H_n^{(u,v)} = \sum_{1 \le j \le k \le n} \frac{1}{j^u k^v}. $$ What are $H_n^{(0,v)}$ and $H_n^{(u,0)}$? Prove the general identity $$ H_n^{(u,v)} + H_n^{(v,u)} = H_n^{(u)}H_n^{(v)} + H_n^{(u+v)}. $$ Verified: no Solve time: - Solution By definition, $$ H_n^{(u,v)}=\sum_{1\le j\le k\le n}\frac1{j^uk^v}. $$ When $u=0$, $$ H_n^{(0,v)} =\sum_{1\le j\le k\le n}\frac1{k^v} =\sum_{k=1}^n\sum_{j=1}^k\frac1{k^v} =\sum_{k=1}^n\frac{k}{k^v} =\sum_{k=1}^n k^{1-v}. $$ Hence $$...
TAOCP 1.2.7 Exercise 15
Section 1.2.7: Harmonic Numbers Exercise 15. [ M23 ] Express $\sum_{k=1}^{n} H_k^2$ in terms of $n$ and $H_n$. Verified: no Solve time: - Solution Let $$ S_n=\sum_{k=1}^{n}H_k^2. $$ We apply summation by parts in the same manner as the derivation of equation (9). Since $$ 1=(k+1)-k, $$ we have $$ H_k^2=(k+1)H_k^2-kH_k^2. $$ Using $$ H_{k+1}=H_k+\frac1{k+1}, $$ it follows that $$ (k+1)H_k^2 =(k+1)\left(H_{k+1}-\frac1{k+1}\right)^2 =(k+1)H_{k+1}^2-2H_{k+1}+\frac1{k+1}. $$ Hence $$ H_k^2 =(k+1)H_{k+1}^2-kH_k^2-2H_{k+1}+\frac1{k+1}. $$ Summing...
TAOCP 1.2.7 Exercise 14
Section 1.2.7: Harmonic Numbers Exercise 14. [ M22 ] Show that $$ \sum_{k=1}^{n}\frac{H_k}{k} = \frac{1}{2}(H_n^2 + H_n^{(2)}), $$ and evaluate $\sum_{k=1}^{n} H_k/(k+1)$. Verified: no Solve time: - Solution Write $$ S_n=\sum_{k=1}^{n}\frac{H_k}{k}. $$ Since $$ H_k=H_{k-1}+\frac1k, $$ we have $$ \frac{H_k}{k}=\frac{H_{k-1}}{k}+\frac1{k^2}. $$ Therefore $$ S_n=\sum_{k=1}^{n}\frac{H_{k-1}}{k}+\sum_{k=1}^{n}\frac1{k^2}. $$ The second sum is $$ \sum_{k=1}^{n}\frac1{k^2}=H_n^{(2)}. $$ For the first sum, $$ \sum_{k=1}^{n}\frac{H_{k-1}}{k} =\sum_{k=1}^{n}\sum_{j=1}^{k-1}\frac1{jk}. $$ Interchanging the order of summation gives $$ \sum_{k=1}^{n}\sum_{j=1}^{k-1}\frac1{jk} =\sum_{1\le j<k\le...
TAOCP 1.2.7 Exercise 3
Section 1.2.7: Harmonic Numbers Exercise 3. [ M21 ] Generalize the argument used in the previous exercise to show that, for $r>1$, the sum $H_n^{(r)}$ remains bounded for all $n$. Find an upper bound. Verified: no Solve time: - Solution Let $$ H_n^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}, \qquad r>1. $$ Exercise 2 treated the case $r=1$ by grouping terms between powers of $2$. The same argument applies here. Choose an integer $m$ such that...
TAOCP 1.2.6 Exercise 59
Section 1.2.6: Binomial Coefficients Exercise 59. [ M25 ] A sequence of numbers $A_{nk}$ satisfies $$ A_{n0}=1,\qquad A_{0k}=\delta_{0k},\qquad A_{nk}=A_{n-1,k}+A_{n-1,k-1}+\binom{n}{k}. $$ Find $A_{nk}$. Verified: no Solve time: - Solution Define $$ B_{nk}=A_{nk}-\binom{n+1}{k}. $$ Then $$ B_{n0}=A_{n0}-\binom{n+1}{0}=1-1=0, $$ and $$ B_{0k}=A_{0k}-\binom{1}{k} =\delta_{0k}-\binom{1}{k}=0 \qquad (k\ge0), $$ since $$ \binom{1}{0}=1,\qquad \binom{1}{1}=1,\qquad \binom{1}{k}=0\quad(k>1). $$ Using the addition formula (9), $$ \binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}. $$ Hence \begin{align*} B_{nk} &=A_{nk}-\binom{n+1}{k} \ &=A_{n-1,k}+A_{n-1,k-1}+\binom{n}{k} -\binom{n}{k}-\binom{n}{k-1} \ &=\bigl(A_{n-1,k}-\binom{n}{k}\bigr) +\bigl(A_{n-1,k-1}-\binom{n}{k-1}\bigr) \...
TAOCP 1.2.6 Exercise 68
Section 1.2.6: Binomial Coefficients Exercise 68. [ M25 ] (A. de Moivre.) Prove that, if $n$ is a nonnegative integer, $$ \sum_k \binom{n}{k}p^k(1-p)^{n-k}|k-np| = 2\lfloor np \rfloor \binom{n}{\lfloor np \rfloor}p^{\lfloor np \rfloor}(1-p)^{n+1-\lfloor np \rfloor}. $$ Verified: no Solve time: - Solution Let $n$ be a nonnegative integer, $0 \le p \le 1$, and let $k$ range over integers $0 \le k \le n$. Define the sum $$ S = \sum_{k=0}^{n}...
TAOCP 1.2.8 Exercise 9
Section 1.2.8: Fibonacci Numbers Exercise 9. [ M20 ] Using the conventions of exercise 8, determine whether Eqs. (4), (6), (14), and (15) still hold when the subscripts are allowed to be any integers. Verified: no Solve time: - Solution By exercise 8, the Fibonacci recurrence $$ F_{n+2}=F_{n+1}+F_n $$ is assumed to hold for all integers $n$. We first determine the values for negative subscripts. Taking $n=-1$ gives $$ F_1=F_0+F_{-1},...
TAOCP 1.2.7 Exercise 17
Section 1.2.7: Harmonic Numbers Exercise 17. [ M24 ] (E. Waring, 1782.) Let $p$ be an odd prime. Show that the numerator of $H_{p-1}$ is divisible by $p$. Verified: no Solve time: - Solution Since $p$ is an odd prime, the integers $$ 1,2,\ldots,p-1 $$ can be paired as $$ k \leftrightarrow p-k, \qquad 1 \le k \le p-1. $$ Therefore $$ H_{p-1} = \sum_{k=1}^{p-1}\frac1k = \frac12\sum_{k=1}^{p-1}\left(\frac1k+\frac1{p-k}\right). $$ Now $$...
TAOCP 1.2.6 Exercise 57
Section 1.2.6: Binomial Coefficients Exercise 57. [ M22 ] Show that the coefficient $a_m$ in Stirling's attempt at generalizing the factorial function is $$ \frac{(-1)^m}{m!}\sum_{k>1}(-1)^k\binom{m-1}{k-1}\ln k. $$ Verified: no Solve time: - Solution Let $$ F(x)=\sum_{m\ge0}a_mx^m $$ be Stirling's attempted generalization of the factorial function. By the construction given earlier in the section, the coefficients $a_m$ are determined from the expansion $$ \ln(1+x) =\sum_{k\ge1}\frac{(-1)^{k-1}}{k}x^k, $$ together with the identity $$...
TAOCP 1.2.7 Exercise 13
Section 1.2.7: Harmonic Numbers Exercise 13. [ M22 ] Prove the identity $$ \sum_{k=1}^{n}\frac{x^k}{k} = H_n + \sum_{k=1}^{n}\binom{n}{k}\frac{(x-1)^k}{k}. $$ Verified: no Solve time: - Solution We prove the identity $$ \sum_{k=1}^{n}\frac{x^k}{k} = H_n + \sum_{k=1}^{n}\binom{n}{k}\frac{(x-1)^k}{k}. $$ Consider the binomial expansion of $x^k$ in terms of $(x-1)$: $$ x^k = \bigl(1 + (x-1)\bigr)^k = \sum_{j=0}^{k}\binom{k}{j}(x-1)^j. $$ Dividing both sides by $k$ and summing over $k$ from $1$ to $n$ gives $$...
TAOCP 1.2.6 Exercise 62
Section 1.2.6: Binomial Coefficients Exercise 62. [ M23 ] Prove the identity $$ \sum_k (-1)^k \binom{l+m}{l+k}\binom{m+n}{m+k}\binom{n+l}{n+k} = \frac{(l+m+n)!}{l!,m!,n!}, \qquad \text{integer } l,m,n \ge 0. $$ Verified: no Solve time: - Solution Let $$ S=\sum_k (-1)^k \binom{l+m}{l+k}\binom{m+n}{m+k}\binom{n+l}{n+k}, \qquad l,m,n\ge0 . $$ We shall evaluate $S$ by extracting a coefficient from a suitable generating function. Using the definition (3), $$ \binom{l+m}{l+k}= x^{,l+k} ^{l+m}, $$ where $[x^r]$ denotes the coefficient of $x^r$. Hence...
TAOCP 1.2.6 Exercise 47
Section 1.2.6: Binomial Coefficients Exercise 47. [ M21 ] Given that $k$ is an integer, show that $$ \binom{r}{k}\binom{r-1/2}{k} = \binom{2r}{k}\binom{2r-k}{k}/4^k = \binom{2r}{2k}\binom{2k}{k}/4^k. $$ Give a simpler formula for the special case $r=-1/2$. Verified: no Solve time: - Solution Let $k$ be an integer. From the definition (3) of generalized binomial coefficients, we have $$ \binom{r}{k} = \frac{r^{\underline{k}}}{k!}, \qquad \binom{r-1/2}{k} = \frac{(r-1/2)^{\underline{k}}}{k!}, $$ where $r^{\underline{k}} = r(r-1)\cdots(r-k+1)$ denotes the falling...
TAOCP 1.2.6 Exercise 17
Section 1.2.6: Binomial Coefficients Exercise 17. [ M18 ] Prove the Chu--Vandermonde formula (21) from Eq. (15), using the idea that $(1+x)^{r+s} = (1+x)^r(1+x)^s$. Verified: yes Solve time: 1m08s Solution Equation (15) is the generalized binomial theorem, $$ (1+x)^r=\sum_{j\ge0}\binom{r}{j}x^j. \tag{15} $$ We compute $(1+x)^{r+s}$ in two ways. First, by Eq. (15), $$ (1+x)^{r+s} =\sum_{n\ge0}\binom{r+s}{n}x^n. \tag{1} $$ Second, $$ (1+x)^{r+s} =(1+x)^r(1+x)^s. $$ Applying Eq. (15) to each factor gives $$ (1+x)^r(1+x)^s...
TAOCP 1.2.6 Exercise 46
Section 1.2.6: Binomial Coefficients Exercise 46. [ M21 ] Using Stirling's approximation, Eq. 1.2.5--(7), find an approximate value of $\binom{x+y}{y}$, assuming that both $x$ and $y$ are large. In particular, find the approximate size of $\binom{2n}{n}$ when $n$ is large. Verified: no Solve time: - Solution By Eq. (5), $$ \binom{x+y}{y}=\frac{(x+y)!}{x!,y!}. $$ Stirling's approximation, Eq. 1.2.5--(7), states that $$ n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n $$ when $n$ is large. Applying this approximation...
TAOCP 1.2.6 Exercise 11
Section 1.2.6: Binomial Coefficients Exercise 11. [ M20 ] (E. Kummer, 1852.) Let $p$ be prime. Show that if $p^n$ divides $\binom{a+b}{a}$ but $p^{n+1}$ does not, then $n$ is equal to the number of carries that occur when $a$ is added to $b$ in the $p$-ary number system. Verified: yes Solve time: 2m16s Solution Let $$ v_p(m) $$ denote the exponent of the highest power of $p$ dividing $m$, and...
TAOCP 1.2.6 Exercise 32
Section 1.2.6: Binomial Coefficients Exercise 32. [ M20 ] Show that $\sum_k \binom{n}{k}x^k = x^{\overline{n}}$, where $x^{\overline{n}}$ is the rising factorial power defined in Eq. 1.2.5--(19). Verified: no Solve time: - Solution By Eq. 1.2.5--(19), the rising factorial power is $$ x^{\overline{n}} = x(x+1)\cdots(x+n-1). $$ We prove that $$ \sum_k \binom{n}{k}x^k = x^{\overline{n}}. $$ Since $\binom{n}{k}=0$ for $k<0$ or $k>n$ by Eq. (3), the sum is finite: $$ \sum_k \binom{n}{k}x^k...
TAOCP 1.2.6 Exercise 30
Section 1.2.6: Binomial Coefficients Exercise 30. [ M24 ] Show that there is a better way to solve Example 3 than the way used in the text, by manipulating the sum so that Eq. (26) applies. Verified: no Solve time: - Solution Example 3 in Section 1.2.6 considers the sum $$ S = \sum_{k=0}^{n} \binom{r+k}{k} \binom{s-k}{n-k}, $$ and in the text, it is evaluated by direct manipulation. We are asked...
TAOCP 1.2.6 Exercise 12
Section 1.2.6: Binomial Coefficients Exercise 12. [ M22 ] Are there any positive integers $n$ for which all the nonzero entries in the $n$th row of Pascal's triangle are odd? If so, find all such $n$. Verified: yes Solve time: 44s Solution Let $$ P(n):\qquad \binom{n}{k}\equiv 1 \pmod 2 \quad\text{for every }k\text{ with }0\le k\le n\text{ and }\binom{n}{k}\ne0. $$ Since $n$ is a positive integer, the nonzero entries in the...
TAOCP 1.2.6 Exercise 33
Section 1.2.6: Binomial Coefficients Exercise 33. [ M20 ] Show that the binomial formula is valid also when it involves factorial powers instead of the ordinary powers. In other words, prove that $$ (x+y)^{\underline{n}} = \sum_k \binom{n}{k}x^{\underline{k}}y^{\underline{n-k}}, \qquad (x+y)^{\overline{n}} = \sum_k \binom{n}{k}x^{\overline{k}}y^{\overline{n-k}}. $$ Verified: no Solve time: - Solution We prove the identities by induction on $n$, using the definitions of falling and rising factorial powers and the standard binomial...
TAOCP 1.2.6 Exercise 34
Section 1.2.6: Binomial Coefficients Exercise 34. [ M23 ] Show that Abel's generalization, Eq. (16), of the binomial formula is true also for rising powers: $$ (x+y)^{\overline{n}} = \sum_k \binom{n}{k}x(x-kz+1)^{\overline{k-1}}(y+kz)^{\overline{n-k}}. $$ Verified: no Solve time: - Solution We prove the stated identity by induction on $n$. The identity to prove is $$ (x+y)^{\overline{n}} = \sum_{k=0}^{n} \binom{n}{k} x(x-kz+1)^{\overline{k-1}} (y+kz)^{\overline{n-k}}. \tag{*} $$ Base case : $n=0$. The left-hand side is $(x+y)^{\overline{0}} =...
TAOCP 1.2.6 Exercise 14
Section 1.2.6: Binomial Coefficients Exercise 14. [ M21 ] Evaluate $\sum_{k=0}^{n} k^4$. Verified: yes Solve time: 29s Solution We seek a closed form for the sum $$ \sum_{k=0}^{n} k^4. $$ By the argument in Section 1.2.6.E, any power $k^m$ can be expressed as a linear combination of binomial coefficients $\binom{k}{j}$ with $0 \le j \le m$. We first determine the coefficients for $k^4$. We look for constants $c_0, c_1, c_2,...
TAOCP 1.2.6 Exercise 20
Section 1.2.6: Binomial Coefficients Exercise 20. [ M20 ] Prove Eq. (24) by using Eqs. (21) and (19), then show that another use of Eq. (19) yields Eq. (25). Verified: no Solve time: 3m17s We use the identities $$ \sum_k \binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n} \tag{21} $$ and $$ \sum_{k=0}^n \binom{k}{m}=\binom{n+1}{m+1}. \tag{19} $$ We first prove Eq. (24), $$ \sum_{k=0}^n \binom{r+k}{k}=\binom{r+n+1}{n}, \tag{24} $$ and then derive Eq. (25) by another application of Eq. (19)....
TAOCP 1.2.6 Exercise 28
Section 1.2.6: Binomial Coefficients Exercise 28. [ M25 ] Prove that $$ \sum_k \binom{r+tk}{k}\binom{s-tk}{n-k} = \sum_{k \ge 0} \binom{r+s-k}{n-k} t^k, $$ if $n$ is a nonnegative integer. Verified: no Solve time: - Solution Let $$ S_n=\sum_k \binom{r+tk}{k}\binom{s-tk}{n-k}, $$ where $n$ is a nonnegative integer. Since $\binom{s-tk}{n-k}=0$ when $k>n$, the sum contains only finitely many nonzero terms. We apply the binomial theorem (13). The coefficient of $x^ny^{r+s-n}$ in $$ (x+y)^{r+s-k}(x+ty)^k $$...
TAOCP 1.2.6 Exercise 19
Section 1.2.6: Binomial Coefficients Exercise 19. [ M18 ] Prove Eq. (23) by induction. Verified: yes Solve time: 38s Solution Equation (23) is $$ \sum_k (-1)^{r-k}\binom{r}{k}\binom{s+k}{n} = \binom{s}{n-r}, \qquad \text{integer } r \ge 0. \tag{23} $$ We prove this identity by induction on $r$. For the basis, let $r=0$. Since $\binom{0}{k}=0$ for $k\ne 0$ and $\binom{0}{0}=1$, the sum reduces to a single term: $$ \sum_k (-1)^{-k}\binom{0}{k}\binom{s+k}{n} = \binom{0}{0}\binom{s}{n} = \binom{s}{n}....
TAOCP 1.2.6 Exercise 50
Section 1.2.6: Binomial Coefficients Exercise 50. [ M20 ] Prove Abel's formula, Eq. (16), in the special case $x+y=0$. Verified: no Solve time: - Solution Let $$ A_n(x,y)=\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(y+n-k)^{n-k}. $$ Abel's formula, Eq. (16), asserts that $$ A_n(x,y)=\frac{(x+y+n)^n}{x}, $$ provided that $x\ne0$. The exercise asks for a proof in the special case $x+y=0$. Put $y=-x$. Then $$ A_n(x,-x) =\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(n-k-x)^{n-k}. $$ We must prove that $$ A_n(x,-x)=\frac{n^n}{x}. \tag{1} $$ Multiply...
TAOCP 1.2.6 Exercise 49
Section 1.2.6: Binomial Coefficients Exercise 49. [ M20 ] Show that the identity $(1+x)^r = (1-x^2)^r(1-x)^{-r}$ implies a relation on binomial coefficients. Verified: no Solve time: - Solution By the binomial theorem (13), $$ (1+x)^r=\sum_{k\ge0}\binom{r}{k}x^k, $$ since the terms with $k<0$ vanish by definition (3). Similarly, $$ (1-x^2)^r=\sum_{j\ge0}\binom{r}{j}(-1)^j x^{2j}, $$ and $$ (1-x)^{-r}=\sum_{m\ge0}\binom{-r}{m}(-1)^m x^m. $$ Hence $$ (1-x^2)^r(1-x)^{-r} = \left(\sum_{j\ge0}\binom{r}{j}(-1)^j x^{2j}\right) \left(\sum_{m\ge0}\binom{-r}{m}(-1)^m x^m\right). $$ Multiplying the series and collecting the...
TAOCP 1.2.6 Exercise 48
Section 1.2.6: Binomial Coefficients Exercise 48. [ M25 ] Show that $$ \sum_{k \ge 0}\binom{n}{k}\frac{(-1)^k}{k+x} = \frac{n!}{x(x+1)\cdots(x+n)} = \frac{1}{x\binom{n+x}{n}}, $$ if the denominators are not zero. Verified: no Solve time: - Solution We are asked to evaluate $$ \sum_{k \ge 0} \binom{n}{k} \frac{(-1)^k}{k+x}. $$ Consider the function $$ f(x) = \int_0^1 t^{x-1} (1-t)^n , dt, $$ which is well defined for $x \notin {0,-1,-2,\dots,-n}$. Expanding $(1-t)^n$ by the binomial theorem,...
TAOCP 1.2.6 Exercise 35
Section 1.2.6: Binomial Coefficients Exercise 35. [ M23 ] Prove the addition formulas (46) for Stirling numbers directly from the definitions, Eqs. (44) and (45). Verified: no Solve time: - Solution We are asked to prove the addition formulas (46) for Stirling numbers directly from their definitions, Eqs. (44) and (45). For clarity, we restate these definitions. The Stirling numbers of the first kind , $c(n,k)$, are defined by $$...
TAOCP 1.2.6 Exercise 51
Section 1.2.6: Binomial Coefficients Exercise 51. [ M21 ] Prove Abel's formula, Eq. (16), by writing $y=(x+y)-x$, expanding the right-hand side in powers of $(x+y)$, and applying the result of the previous exercise. Verified: no Solve time: - Solution We are asked to prove Abel's formula, Eq. (16), using the hint: write $y=(x+y)-x$, expand in powers of $(x+y)$, and apply the result of Exercise 50. Abel's formula states, for arbitrary...
TAOCP 1.2.6 Exercise 10
Section 1.2.6: Binomial Coefficients Exercise 10. [ M25 ] If $p$ is prime, show that: $\binom{n}{p} \equiv \lfloor n/p \rfloor \pmod p$. $\binom{p}{k} \equiv 0 \pmod p$, for $1 \le k \le p-1$. $\binom{p-1}{k} \equiv (-1)^k \pmod p$, for $0 \le k \le p-1$. $\binom{p+1}{k} \equiv 0 \pmod p$, for $2 \le k \le p-1$. (E. Lucas, 1877.) $$ \binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \binom{n \bmod p}{k \bmod...
TAOCP 1.2.6 Exercise 22
Section 1.2.6: Binomial Coefficients Exercise 22. [ M20 ] Prove Eq. (26) for the special case $s=(n-1)r+nt$. Verified: yes Solve time: 4m15s Let $$ S=\sum_{i=0}^{s}\binom{r+i}{r}\binom{t+s-i}{t}, \qquad s=(n-1)r+nt. $$ We shall prove, using only identity (11), $$ \sum_{m=0}^{M}\binom{p+m}{p} =\binom{p+M+1}{p+1}, \tag{11} $$ that $$ S=\binom{r+t+s+1}{r+t+1}. $$ Substituting $s=(n-1)r+nt$ will then give the required special case of Eq. (26). From (11), $$ \binom{r+i}{r} =\sum_{k=0}^{i}\binom{r-1+k}{r-1}. $$ Substituting into $S$ and reversing the order of...
TAOCP 1.2.6 Exercise 29
Section 1.2.6: Binomial Coefficients Exercise 29. [ M20 ] Show that Eq. (34) is just a special case of the general identity proved in exercise 1.2.3--33. Verified: no Solve time: - Solution Equation (34) states that for integers $r \ge 0$ and $m$, $$ \sum_k \binom{r}{k}(-1)^{r-k}k^m = \begin{cases} 0, & 0 \le m < r,\ r!, & m=r. \end{cases} \tag{34} $$ The general identity proved in exercise 1.2.3, 33 is...
TAOCP 1.2.6 Exercise 31
Section 1.2.6: Binomial Coefficients Exercise 31. [ M20 ] Evaluate $$ \sum_k \binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n} $$ in terms of $r$, $s$, $m$, and $n$, given that $m$ and $n$ are integers. Begin by replacing $$ \binom{r+k}{m+n} $$ by $\sum_j \binom{r}{m+n-j}\binom{k}{j}$. Verified: no Solve time: - Solution Let $$ S=\sum_k \binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n}. $$ The exercise directs us to expand the last factor by Vandermonde's convolution: $$ \binom{r+k}{m+n} = \sum_j \binom{r}{m+n-j}\binom{k}{j}. $$ Hence $$ S...
TAOCP 1.2.4 Exercise 31
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 31. [ M22 ] Prove that if $f(n)$ is multiplicative, so is $$g(n)=\sum_{d \mid n} f(d).$$ Verified: yes Solve time: 33s Solution Let $f(n)$ be a multiplicative function, and define $g(n) = \sum_{d \mid n} f(d).$ We want to show that $g$ is multiplicative, that is, for any integers $r \perp s$, $g(rs) = g(r) g(s).$ Since $r \perp s$, every...
TAOCP 1.2.4 Exercise 21
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 21. [ M22 ] ( Fundamental theorem of arithmetic. ) Use Law B and exercise 1.2.1–5 to prove that every integer $n>1$ has a unique representation as a product of primes (except for the order of the factors). In other words, show that there is exactly one way to write $$n=p_1p_2\cdots p_k,$$ where each $p_j$ is prime and $p_1 \le p_2...
TAOCP 1.2.4 Exercise 33
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 33. [ M18 ] Given that $m$ and $n$ are integers, evaluate (a) $\left\lfloor \tfrac12(n+m)\right\rfloor + \left\lfloor \tfrac12(n-m+1)\right\rfloor$; (b) $\left\lceil \tfrac12(n+m)\right\rceil + \left\lceil \tfrac12(n-m+1)\right\rceil$. (The special case $m=0$ is worth noting.) Verified: no Solve time: 32s Solution Let $m$ and $n$ be integers. We first evaluate the sum in part (a): $S_a = \left\lfloor \frac{n+m}{2} \right\rfloor + \left\lfloor \frac{n-m+1}{2} \right\rfloor.$ Write...
TAOCP 1.2.4 Exercise 36
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 36. [ M23 ] Prove that $\sum_{k=1}^n \lfloor k/2 \rfloor = \lfloor n^2/4 \rfloor$; also evaluate $\sum_{k=1}^n \lceil k/2 \rceil$. Verified: yes Solve time: 45s Solution We first evaluate $$ S_n=\sum_{k=1}^n \left\lfloor \frac{k}{2}\right\rfloor. $$ Separate the terms according to parity. If $n=2m$ is even, then $$ \left\lfloor \frac{2j-1}{2}\right\rfloor=j-1, \qquad \left\lfloor \frac{2j}{2}\right\rfloor=j, \qquad (1\le j\le m). $$ Hence $$ S_{2m} = \sum_{j=1}^m\left(...
TAOCP 1.2.4 Exercise 24
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 24. ▶ [ M20 ] To what extent can Laws A, B, C, and D be generalized to apply to arbitrary real numbers instead of integers? Verified: no Solve time: 41s Solution Law A extends without change to arbitrary real numbers. Suppose $$ a \equiv b \pmod m,\qquad x \equiv y \pmod m, $$ where congruence is defined by equation (5):...
TAOCP 1.2.4 Exercise 41
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 41. [ M23 ] Let $a_1,a_2,a_3,\ldots$ be the sequence $1,2,2,3,3,3,4,4,4,4,\ldots$; find an expression for $a_n$ in terms of $n$, using the floor and/or ceiling function. Verified: no Solve time: 28s Solution The sequence is formed by repeating each positive integer $k$ exactly $k$ times: $$ 1,\ 2,2,\ 3,3,3,\ 4,4,4,4,\ \ldots $$ Hence $a_n=k$ precisely when $n$ lies in the block occupied...
TAOCP 1.2.4 Exercise 44
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 44. [ M24 ] Show that $$\sum_{k\ge0}\sum_{1 \le j < b} \left\lfloor \frac{n+j b^k}{b^{k+1}} \right\rfloor = n,$$ if $b$ and $n$ are integers, $n \ge 0$, and $b \ge 2$. What is the value of this sum when $n<0$? Verified: yes Solve time: 1m33s Solution Let $$ S(n)=\sum_{k\ge0}\sum_{1\le j<b}\left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor . $$ Since $b\ge2$, for fixed $n$ the terms vanish...
TAOCP 1.2.4 Exercise 35
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 35. ▶ [ M20 ] Given that $m$ and $n$ are integers and $n>0$, prove that $$\left\lfloor \frac{x+m}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor + m}{n} \right\rfloor$$ for all real $x$. (When $m=0$, we have an important special case.) Does an analogous result hold for the ceiling function? Verified: yes Solve time: 1m18s Solution Let $x$ be a real number, and...
TAOCP 1.2.4 Exercise 32
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 32. [ M18 ] Prove the double-summation identity $$\sum_{d \mid n}\sum_{c \mid d} f(c,d)=\sum_{c \mid n}\sum_{d \mid (n/c)} f(c,cd),$$ for any function $f(x,y)$. Verified: yes Solve time: 2m11s Solution Every divisor pair $(c,d)$ that appears on the left-hand side satisfies $$ c \mid d,\qquad d \mid n. $$ Hence there exists an integer $e$ such that $$ d=ce. $$ Since $d...
TAOCP 1.2.4 Exercise 29
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 29. [ M22 ] A function $f(n)$ of positive integers $n$ is called multiplicative if $f(rs)=f(r)f(s)$ whenever $r \perp s$. Show that each of the following functions is multiplicative: (a) $f(n)=n^c$, where $c$ is any constant; (b) $f(n)=[n \text{ is not divisible by } k^2 \text{ for any integer } k>1]$; (c) $f(n)=c^k$, where $k$ is the number of distinct primes...
TAOCP 1.2.4 Exercise 42
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 42. [ M24 ] (a) Prove that $$\sum_{k=1}^n a_k = na_n - \sum_{k=1}^{n-1} k(a_{k+1}-a_k),\qquad \text{if } n>0.$$ (b) The preceding formula is useful for evaluating certain sums involving the floor function. Prove that, if $b$ is an integer $\ge 2$, $$ \sum_{k=1}^n \lfloor \log_b k \rfloor = (n+1)\lfloor \log_b n \rfloor - \frac{b^{\lfloor \log_b n \rfloor +1}-b}{b-1}. $$ Verified: no Solve...
TAOCP 1.2.4 Exercise 28
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 28. ▶ [ M25 ] Show that the method used to prove Theorem F can be used to prove the following extension, called Euler’s theorem : $a^{\varphi(m)} \equiv 1$ (modulo $m$), for any positive integer $m$, when $a \perp m$. (In particular, the number $n'$ in exercise 19 may be taken to be $n^{\varphi(m)-1} \bmod m$.) Verified: yes Solve time: 39s...
TAOCP 1.2.4 Exercise 43
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 43. [ M23 ] Evaluate $\sum_{k=1}^n \lfloor \sqrt{k} \rfloor$. Verified: yes Solve time: 2m17s Solution We wish to evaluate $S_n = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor.$ Let $m = \lfloor \sqrt{n} \rfloor$, so that $m^2 \le n < (m+1)^2$. Observe that for any integer $i \ge 0$, the numbers $k$ satisfying $i^2 \le k < (i+1)^2$ all have $\lfloor \sqrt{k} \rfloor =...
TAOCP 1.2.4 Exercise 34
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 34. ▶ [ M21 ] What conditions on the real number $b>1$ are necessary and sufficient to guarantee that $\lfloor \log_b x \rfloor = \lfloor \log_b \lfloor x \rfloor \rfloor$ for all real $x \ge 1$? Verified: no Solve time: 4m59s Solution We seek all real numbers $b>1$ such that $$ \lfloor \log_b x\rfloor=\lfloor \log_b \lfloor x\rfloor\rfloor \qquad (x\ge 1). $$...
TAOCP 1.2.3 Exercise 43
Section 1.2.3: Sums and Products Exercise 43. [ M24 ] What is the sum of all $n^2$ elements in the inverse of Vandermonde’s matrix? [Hint: Use exercise 33.] Verified: yes Solve time: 39s Solution Let $V = (v_{ij})$ be the $n \times n$ Vandermonde matrix with entries $v_{ij} = x_i^{j-1}$ for $1 \le i, j \le n$, and let $B = (b_{ij})$ denote its inverse. By Exercise 40, each element...
TAOCP 1.2.3 Exercise 42
Section 1.2.3: Sums and Products Exercise 42. [ M18 ] What is the sum of all $n^2$ elements in the inverse of the combinatorial matrix? Verified: yes Solve time: 35s Solution By Exercise 39, the inverse of the combinatorial matrix has entries $$ b_{ij}=\frac{-y+\delta_{ij}(x+ny)}{x(x+ny)}. $$ We must compute $$ \sum_{1\le i\le n}\sum_{1\le j\le n} b_{ij}. $$ Using Eq. (8), $$ \sum_{i=1}^n\sum_{j=1}^n b_{ij} = \frac1{x(x+ny)} \left( \sum_{i=1}^n\sum_{j=1}^n (-y) + \sum_{i=1}^n\sum_{j=1}^n \delta_{ij}(x+ny)...
TAOCP 1.2.3 Exercise 32
Section 1.2.3: Sums and Products Exercise 32. [ M20 ] Prove that $$\prod_{j=1}^n \sum_{i=1}^m a_{ij} = \sum_{1 \le i_1, \ldots, i_n \le m} a_{i_1 1} \ldots a_{i_n n}.$$ Verified: yes Solve time: 29s Solution We proceed by induction on $n$. Base case: Let $n = 1$. Then the left-hand side is $\prod_{j=1}^1 \sum_{i=1}^m a_{i1} = \sum_{i=1}^m a_{i1}.$ The right-hand side is $\sum_{1 \le i_1 \le m} a_{i_1 1} = \sum_{i=1}^m...
TAOCP 1.2.3 Exercise 40
Section 1.2.3: Sums and Products Exercise 40. [ M24 ] Show that the inverse of Vandermonde’s matrix is given by $$b_{ij} = \left( \sum_{\substack{1 \le k_1 < \cdots < k_{n-j} \le n \ k_1, \ldots, k_{n-j} \ne i}} (-1)^{j-1} x_{k_1} \ldots x_{k_{n-j}} \right) \bigg/ x_i \prod_{\substack{1 \le k \le n \ k \ne i}} (x_k - x_i).$$ Don’t be dismayed by the complicated sum in the numerator, it is just...
TAOCP 1.2.3 Exercise 30
Section 1.2.3: Sums and Products Exercise 30. ▶ [ M23 ] (J. Binet, 1812.) Without using induction, prove the identity $$\left( \sum_{j=1}^n a_j x_j \right) \left( \sum_{j=1}^n b_j y_j \right) = \left( \sum_{j=1}^n a_j y_j \right) \left( \sum_{j=1}^n b_j x_j \right) + \sum_{1 \le j < k \le n} (a_j b_k - a_k b_j)(x_j y_k - x_k y_j).$$ [An important special case arises when $w_1, \ldots, w_n, z_1, \ldots, z_n$...
TAOCP 1.2.3 Exercise 37
Section 1.2.3: Sums and Products Exercise 37. ▶ [ M24 ] Show that the determinant of Vandermonde’s matrix is $$\prod_{1 \le j \le n} x_j \prod_{1 \le i < j \le n} (x_j - x_i).$$ Verified: yes Solve time: 33s Solution Let $V_n = (a_{ij}) {1 \le i,j \le n}$ denote the $n \times n$ Vandermonde matrix, where $a {ij} = x_j^i$. We aim to show that $\det(V_n) = \prod_{1...
TAOCP 1.2.3 Exercise 34
Section 1.2.3: Sums and Products Exercise 34. [ M25 ] Prove that $$\sum_{k=1}^n \frac{\prod_{1 \le r \le n, , r \ne m} (x + k - r)}{\prod_{1 \le r \le n, , r \ne k} (k - r)} = 1,$$ provided that $1 \le m \le n$ and $x$ is arbitrary. For example, if $n = 4$ and $m = 2$, then $$\frac{x(x-2)(x-3)}{(-1)(-2)(-3)} + \frac{(x+1)(x-1)(x-2)}{(1)(-1)(-2)} + \frac{(x+2)x(x-1)}{(2)(1)(-1)} + \frac{(x+3)(x+1)x}{(3)(2)(1)} =...
TAOCP 1.2.3 Exercise 31
Section 1.2.3: Sums and Products Exercise 31. [ M20 ] Use Binet’s formula to express the sum $\sum_{1 \le j < k \le n} (u_j - u_k)(v_j - v_k)$ in terms of $\sum_{j=1}^n u_j v_j$, $\sum_{j=1}^n u_j$, and $\sum_{j=1}^n v_j$. Verified: yes Solve time: 1m06s Solution Apply Binet's formula from Exercise 30 with the substitutions $$ a_j=u_j,\qquad b_j=1,\qquad x_j=1,\qquad y_j=v_j. $$ Then $$ \left(\sum_{j=1}^n u_j\right)\left(\sum_{j=1}^n v_j\right) = \left(\sum_{j=1}^n u_jv_j\right)\left(\sum_{j=1}^n 1\right)...
TAOCP 1.2.3 Exercise 45
Section 1.2.3: Sums and Products Exercise 45. ▶ [ M25 ] A Hilbert matrix , sometimes called an $n \times n$ segment of the (infinite) Hilbert matrix, is a matrix for which $a_{ij} = 1/(i + j - 1)$. Show that this is a special case of Cauchy’s matrix, find its inverse, show that each element of the inverse is an integer, and show that the sum of all elements...
TAOCP 1.2.3 Exercise 36
Section 1.2.3: Sums and Products Exercise 36. [ M23 ] Show that the determinant of the combinatorial matrix is $x^{n-1}(x + ny)$. Verified: yes Solve time: 45s Solution Let $A = (a_{ij})$ be the $n \times n$ combinatorial matrix with entries $a_{ij} = y + \delta_{ij} x = \begin{cases} x + y, & i = j, \ y, & i \ne j. \end{cases}$ We want to show that $\det(A) =...
TAOCP 1.2.3 Exercise 18
Section 1.2.3: Sums and Products Exercise 18. [ M20 ] Show how to interchange the order of summation as in Eq. (9) given that $R(i)$ is the relation “$n$ is a multiple of $i$” and $S(i, j)$ is the relation “$1 \le j < i$.” Verified: yes Solve time: 34s Solution We are to transform $\sum_{R(i)} \sum_{S(i,j)} a_{ij}$ according to Eq. (9), where $R(i) : \text{``$n$ is a multiple of...
TAOCP 1.2.3 Exercise 21
Section 1.2.3: Sums and Products Exercise 21. ▶ [ M25 ] Derive rule (d) from (8) and (17). Verified: yes Solve time: 34s Solution By Eq. (17), $$ \sum_{R(j)} a_j = \sum_j a_j [R(j)], \qquad \sum_{S(j)} a_j = \sum_j a_j [S(j)]. $$ Therefore $$ \sum_{R(j)} a_j + \sum_{S(j)} a_j = \sum_j a_j [R(j)] + \sum_j a_j [S(j)]. $$ Applying Eq. (8), $$ \sum_{R(j)} a_j + \sum_{S(j)} a_j = \sum_j a_j...
TAOCP 1.2.3 Exercise 27
Section 1.2.3: Sums and Products Exercise 27. [ M20 ] Generalize the result of exercise 1.2.1–9 by proving that $$\prod_{j=1}^n (1 - a_j) \ge 1 - \sum_{j=1}^n a_j,$$ assuming that $0 < a_j < 1$. Verified: yes Solve time: 41s Solution We proceed by induction on $n$. Base case ($n = 1$): We have $\prod_{j=1}^1 (1 - a_j) = 1 - a_1,$ and $1 - \sum_{j=1}^1 a_j = 1 -...
TAOCP 1.2.3 Exercise 38
Section 1.2.3: Sums and Products Exercise 38. ▶ [ M25 ] Show that the determinant of Cauchy’s matrix is $$\prod_{1 \le i < j \le n} (x_j - x_i)(y_j - y_i) \bigg/ \prod_{1 \le i, j \le n} (x_i + y_j).$$ Verified: yes Solve time: 5m11s Let $$ D_n=\det!\left(\frac1{x_i+y_j}\right)_{1\le i,j\le n}. $$ We shall prove that $$ D_n= \frac{\displaystyle\prod_{1\le i<j\le n}(x_j-x_i)(y_j-y_i)} {\displaystyle\prod_{1\le i,j\le n}(x_i+y_j)}. $$ For each row $i$, multiply...
TAOCP 1.2.3 Exercise 39
Section 1.2.3: Sums and Products Exercise 39. [ M23 ] Show that the inverse of a combinatorial matrix is a combinatorial matrix with the entries $b_{ij} = (-y + \delta_{ij}(x + ny)) / x(x + ny)$. Verified: yes Solve time: 2m20s Solution Let $A = (a_{ij})_{1 \le i,j \le n}$ be the combinatorial matrix, where $a_{ij} = x\delta_{ij} + y.$ Thus $A = xI + yJ,$ where $I$ is the...
TAOCP 1.2.3 Exercise 28
Section 1.2.3: Sums and Products Exercise 28. [ M22 ] Find a simple formula for $\prod_{j=2}^n (1 - 1/j^2)$. Verified: yes Solve time: 35s Solution Write $$ 1-\frac1{j^2} = \frac{(j-1)(j+1)}{j^2} = \frac{j-1}{j}\cdot\frac{j+1}{j}. $$ Hence $$ \prod_{j=2}^n \left(1-\frac1{j^2}\right) = \prod_{j=2}^n \frac{j-1}{j} \prod_{j=2}^n \frac{j+1}{j}, $$ by the distributive law for products. Now $$ \prod_{j=2}^n \frac{j-1}{j} = \frac12\cdot\frac23\cdot\frac34\cdots\frac{n-1}{n} = \frac1n, $$ since all intermediate factors cancel. Similarly, $$ \prod_{j=2}^n \frac{j+1}{j} = \frac32\cdot\frac43\cdot\frac54\cdots\frac{n+1}{n} =...
TAOCP 1.2.2 Exercise 27
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 27. ▶ [ M25 ] Consider the method for calculating $\log_{10} x$ discussed in the text. Let $x' k$ denote the computed approximation to $x_k$, determined as follows: $x(1 - \delta) \le 10^n x' 0 \le x(1 + \epsilon)$; and in the determination of $x' k$ by Eqs. (18), the quantity $y_k$ is used in place of $(x' {k-1})^2$, where $(x' {k-1})^2(1 -...
TAOCP 1.2.3 Exercise 16
Section 1.2.3: Sums and Products Exercise 16. [ M22 ] Prove that $$\sum_{j=0}^n jx^j = \frac{nx^{n+2} - (n+1)x^{n+1} + x}{(x-1)^2},$$ if $x \ne 1$, without using mathematical induction. Verified: yes Solve time: 31s Solution Let $$ S=\sum_{j=0}^n jx^j. $$ Since the term corresponding to $j=0$ is zero, $$ S=\sum_{j=1}^n jx^j. $$ Multiply by $x$: $$ xS=\sum_{j=1}^n jx^{j+1}. $$ By rule (b), replacing $j$ by $j-1$, $$ xS=\sum_{j=2}^{n+1} (j-1)x^j. $$ Now...
TAOCP 1.2.11.3 Exercise 18
Section 1.2.11.3: Some Asymptotic Calculations Exercise 18. [ M25 ] Show that the sums $$ \sum \binom{n}{k} k^k (n-k)^{n-k} \qquad \text{and} \qquad \sum \binom{n}{k} (k+1)^k (n-k)^{n-k} $$ can be expressed very simply in terms of the $Q$ function. Verified: yes Solve time: 4m43s Let $$ Q(n)=\frac{1}{n!}\sum_{k=0}^{n}\binom{n}{k}k^k(n-k)^{n-k}, \qquad 0^0=1. $$ 1. First sum $$ S_1(n)=\sum_{k=0}^{n}\binom{n}{k}k^k(n-k)^{n-k}. $$ By definition of $Q(n)$, $$ S_1(n)=n!Q(n). $$ 2. Second sum $$ S_2(n)=\sum_{k=0}^{n}\binom{n}{k}(k+1)^k(n-k)^{n-k}. $$ Step 1:...
TAOCP 1.2.2 Exercise 7
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 7. [ M23 ] Given that $x$ and $y$ are integers, prove the laws of exponents, starting from the definition given by Eq. (4). Verified: yes Solve time: 11m16s Assume throughout that $b\neq 0$. The recursive definition of integer powers is $$ b^0=1, $$ $$ b^n=b^{n-1}b \qquad (n>0), $$ $$ b^n=\frac{b^{n+1}}{b} \qquad (n<0). $$ We shall prove the exponent laws $$ b^{x+y}=b^x b^y,...
TAOCP 1.2.3 Exercise 15
Section 1.2.3: Sums and Products Exercise 15. ▶ [ M22 ] Compute the sum $1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + n \times 2^n$ for small values of $n$. Do you see the pattern developing in these numbers? If not, discover it by manipulations similar to those leading up to Eq. (14). Verified: yes Solve time: 1m15s Solution Let $$ S_n=\sum_{j=1}^{n} j2^j. $$...
TAOCP 1.2.2 Exercise 9
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 9. [ M23 ] Given that $x$ and $y$ are rational, prove the laws of exponents under the assumption that the laws hold when $x$ and $y$ are integers. Verified: yes Solve time: 2m06s Solution Let $$ x=\frac pq,\qquad y=\frac rs, $$ where $p,r\in\mathbb Z$ and $q,s\in\mathbb Z_{>0}$. By Eq. (6), $$ b^{p/q}=\sqrt[q]{,b^p,}, $$ so rational powers are defined in terms of positive...
TAOCP 1.2.2 Exercise 23
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 23. [ M25 ] Give a geometric proof that $\ln xy = \ln x + \ln y$, based on Fig. 6. Verified: yes Solve time: 1m51s Solution Let $$ L(z) $$ denote the area under the hyperbola $$ y=\frac1t $$ between $t=1$ and $t=z$. Figure 6 defines the natural logarithm by this area: $$ L(z)=\ln z. $$ We must prove geometrically that $$...
TAOCP 1.2.2 Exercise 13
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 13. ▶ [ M23 ] (a) Given that $x$ is a positive real number and $n$ is a positive integer, prove the inequality $\sqrt[n]{1 + x} - 1 \le x/n$. (b) Use this fact to justify the remarks following (7). Verified: yes Solve time: 36s Solution (a) Let $$ u=\sqrt[n]{1+x}. $$ Then $u>0$ and $$ u^n=1+x. $$ Since $$ u^n-1=(u-1)(u^{n-1}+u^{n-2}+\cdots+u+1), $$ we have...
TAOCP 1.2.10 Exercise 20
Section 1.2.10: Analysis of an Algorithm Exercise 20. [ M22 ] Suppose we want to calculate $\max{|a_1-b_1|,|a_2-b_2|,\ldots,|a_n-b_n|}$ when $b_1 \le b_2 \le \cdots \le b_n$. Show that it is sufficient to calculate $\max{m_L,m_R}$, where $$ m_L = \max{a_k-b_k \mid a_k \text{ is a left-to-right maximum of } a_1a_2\ldots a_n}, $$ $$ m_R = \max{b_k-a_k \mid a_k \text{ is a right-to-left minimum of } a_1a_2\ldots a_n}. $$ Verified: yes Solve time:...
TAOCP 1.2.10 Exercise 10
Section 1.2.10: Analysis of an Algorithm Exercise 10. [ M20 ] Combine the results of the preceding three exercises to obtain a formula for the probability that $A=k$ under the assumption that each $X$ is selected at random from a set of $M$ objects. Verified: yes Solve time: 4m16s Solution We are asked to determine the probability distribution of $A$, the number of times step M4 is executed, when each...
TAOCP 1.2.10 Exercise 8
Section 1.2.10: Analysis of an Algorithm Exercise 8. [ M20 ] Suppose that each $X[k]$ is taken at random from a set of $M$ distinct elements, so that each of the $M^n$ possible choices for $X[1],X[2],\ldots,X[n]$ is considered equally likely. What is the probability that all the $X[k]$ will be distinct? Verified: yes Solve time: 4m36s Solution Let $E$ be the event that all of the values $X[1],X[2],\ldots,X[n]$ are distinct....
TAOCP 1.2.1 Exercise 10
Section 1.2.1: Mathematical Induction Exercise 10. [ M22 ] Prove by induction that if $n \ge 10$, then $2^n > n^3$. Verified: yes Solve time: 37s Solution Let $P(n)$ be the statement $$ 2^n > n^3. $$ We will prove by induction that $P(n)$ is true for all integers $n \ge 10$. First, consider the basis step. When $n=10$, $$ 2^{10}=1024 $$ and $$ 10^3=1000. $$ Since $$ 1024>1000, $$...
TAOCP 1.2.1 Exercise 13
Section 1.2.1: Mathematical Induction Exercise 13. ▶ [ M23 ] Extend Algorithm E by adding a new variable $T$ and adding the operation “$T \leftarrow T + 1$” at the beginning of each step. (Thus, $T$ is like a clock, counting the number of steps executed.) Assume that $T$ is initially zero, so that assertion A1 in Fig. 4 becomes “$m > 0$, $n > 0$, $T = 0$.” The...
TAOCP 1.2.11.2 Exercise 9
Section 1.2.11.2: Euler's Summation Formula Exercise 9. [ M25 ] Find the asymptotic value of $\binom{2n}{n}$ with a relative error of $O(n^{-3})$, in two ways. 1.2.11.3. Some asymptotic calculations. In this subsection we shall investigate the following three intriguing sums, in order to deduce their approximate values: $$ P(n) = 1 + \frac{n-1}{n} + \frac{(n-2)^2}{n(n-1)} + \cdots = \sum_{k=0}^{n} \frac{(n-k)^k (n-k)!}{n!}, \tag{1} $$ $$ Q(n) = 1 + \frac{n-1}{n} +...
TAOCP 1.2.10 Exercise 16
Section 1.2.10: Analysis of an Algorithm Exercise 16. [ M25 ] Suppose $X$ is a random variable whose values are a mixture of the probability distributions generated by $g_1(z),g_2(z),\ldots,g_r(z)$, in the sense that it uses $g_k(z)$ with probability $p_k$, where $p_1+\cdots+p_r=1$. What is the generating function for $X$? Express the mean and variance of $X$ in terms of the means and variances of $g_1,g_2,\ldots,g_r$. Verified: yes Solve time: 41s Solution...
TAOCP 1.2.11.2 Exercise 8
Section 1.2.11.2: Euler's Summation Formula Exercise 8. [ M23 ] Find the asymptotic value of $\ln((an^2+bn)!)$ with absolute error $O(n^{-2})$. Verified: yes Solve time: 45s Solution Let $$ m = an^2 + bn, \qquad a>0. $$ By Stirling’s formula in logarithmic form, $$ \ln(m!) = m\ln m - m + \frac{1}{2}\ln(2\pi m) + \frac{1}{12m} + O!\left(\frac{1}{m^3}\right). \tag{22} $$ Since $m = \Theta(n^2)$, the remainder term satisfies $O(1/m^3)=O(n^{-6})$, which is absorbed...
TAOCP 1.2.10 Exercise 9
Section 1.2.10: Analysis of an Algorithm Exercise 9. [ M25 ] Generalize the result of the preceding exercise to find a formula for the probability that exactly $m$ distinct values occur among the $X$'s. Express your answer in terms of Stirling numbers. Verified: yes Solve time: 1m30s Solution Let $X[1],X[2],\ldots,X[n]$ be chosen independently and uniformly from a set of $M$ distinct elements. We are asked to determine the probability that...
TAOCP 1.2.11.2 Exercise 1
Section 1.2.11.2: Euler's Summation Formula Exercise 1. [ M18 ] Prove Eq. (7). Verified: yes Solve time: 1m44s Corrected Solution We are asked to prove Eq. (7) of Section 1.2.11.2 , which is the Euler–Maclaurin summation formula: $$ \sum_{k=m}^{n} f(k) = \int_m^n f(x),dx + \frac{f(m)+f(n)}{2} + \sum_{r=1}^{p} \frac{B_{2r}}{(2r)!}\bigl(f^{(2r-1)}(n)-f^{(2r-1)}(m)\bigr) + R_p, $$ where $B_{2r}$ are Bernoulli numbers, $f^{(r)}$ is the $r$-th derivative of $f$, and $R_p$ is a remainder term. We...
TAOCP 1.2.1 Exercise 12
Section 1.2.1: Mathematical Induction Exercise 12. [ M25 ] Show how Algorithm E can be generalized as stated in the text so that it will accept input values of the form $u + v\sqrt{2}$, where $u$ and $v$ are integers, and the computations can still be done in an elementary way (that is, without using the infinite decimal expansion of $\sqrt{2}$). Prove that the computation will not terminate, however, if...
TAOCP 1.2.10 Exercise 19
Section 1.2.10: Analysis of an Algorithm Exercise 19. [ M21 ] If $a_k>a_j$ for $1 \le j<k$, we say that $a_k$ is a left-to-right maximum of the sequence $a_1a_2\ldots a_n$. Suppose $a_1a_2\ldots a_n$ is a permutation of ${1,2,\ldots,n}$, and let $b_1b_2\ldots b_n$ be the inverse permutation, so that $a_k=l$ if and only if $b_l=k$. Show that $a_k$ is a left-to-right maximum of $a_1a_2\ldots a_n$ if and only if $k$ is...
TAOCP 1.2.11.3 Exercise 3
Section 1.2.11.3: Some Asymptotic Calculations Exercise 3. [ M20 ] Derive Eq. (8) from Eq. (7). Verified: yes Solve time: 1m10s Solution From Eq. (7), $$ \gamma(a,x)=\sum_{k\ge 0}\frac{(-1)^k x^{k+a}}{k!(k+a)}. $$ Multiply both sides by $e^x=\sum_{m\ge 0} \frac{x^m}{m!}$: $$ e^x\gamma(a,x) =\left(\sum_{m\ge 0}\frac{x^m}{m!}\right)\left(\sum_{k\ge 0}\frac{(-1)^k x^{k+a}}{k!(k+a)}\right). $$ Collect the coefficient of $x^{n+a}$ in the Cauchy product. Writing $n=m+k$, $$ e^x\gamma(a,x) =\sum_{n\ge 0} x^{n+a}\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!(k+a)}. $$ Define $$ C_n=\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!(k+a)}. $$ The coefficient in...
TAOCP 1.2.11.3 Exercise 16
Section 1.2.11.3: Some Asymptotic Calculations Exercise 16. [ M24 ] Prove the identity $$ \sum_k (-1)^k \binom{n}{k} k^{n-1} Q(k) = (-1)^n (n-1)!, \qquad \text{when } n>0. $$ Verified: no Solve time: 5m13s Setup We are asked to prove the identity $$ \sum_{k=0}^{n} (-1)^k \binom{n}{k} k^{,n-1} Q(k) = (-1)^n (n-1)!, \qquad n>0, $$ where $$ Q(k) = \int_0^\infty \left(1+\frac{z}{k}\right)^k e^{-z} dz. $$ The exercise refers to the definition of $Q(k)$ in...