#math-medium
TAOCP 4.6.4 Exercise 19
Section 4.6.4: Evaluation of Polynomials Exercise 19. ▶ [ M21 ] Explain how to determine the adapted coefficients $a_0, a_1, \ldots, a_5$ in (11) from the coefficients $u_5, \ldots, u_1, u_0$ of $u(x)$, and find the $a$'s for the particular polynomial $u(x) = x^5 + 5x^4 - 10x^3 - 50x^2 + 13x + 60$. Verified: yes Solve time: 1m09s Correctness The proposed solution does not answer the exercise that was...
TAOCP 4.6.4 Exercise 17
Section 4.6.4: Evaluation of Polynomials Exercise 17. [ M20 ] Show that the interpolation formula (45) reduces to a very simple expression involving binomial coefficients when $x_k = x_0 + kh$ for $0 \le k \le n$. [ Hint: See exercise 1.2.6–48.] Verified: yes Solve time: 1m13s Solution We are asked to simplify the interpolation formula (45) when the nodes are equally spaced, that is, when $x_k = x_0 +...
TAOCP 4.6.4 Exercise 16
Section 4.6.4: Evaluation of Polynomials Exercise 16. [ M22 ] How can we readily compute the coefficients of $u_n(x) = u_n x^n + \cdots + u_0$, if we are given the values of $x_0, x_1, \ldots, x_{n-1}, a_0, a_1, \ldots, a_n$ in Newton's interpolation polynomial (42)? Verified: yes Solve time: 1m11s Solution Newton's interpolation polynomial (42) has the form $$ u_n(x) = a_0 +a_1(x-x_0) +a_2(x-x_0)(x-x_1) +\cdots +a_n\prod_{0\le j<n}(x-x_j). $$ We...
TAOCP 4.6.4 Exercise 13
Section 4.6.4: Evaluation of Polynomials Exercise 13. [ M23 ] Find the inverse of the general discrete Fourier transform (37), by expressing $F(t_1, \ldots, t_n)$ in terms of the values of $f(s_1, \ldots, s_n)$. [ Hint: See Eq. 1.2.9–(13).] Verified: yes Solve time: 1m16s Solution Let the general discrete Fourier transform (37) be $$ f(s_1,\ldots,s_n) = \sum_{t_1=0}^{m_1-1} \cdots \sum_{t_n=0}^{m_n-1} F(t_1,\ldots,t_n) , \omega_1^{,s_1t_1} \cdots \omega_n^{,s_nt_n}, \tag{37} $$ where $$ \omega_j=e^{2\pi i/m_j},...
TAOCP 4.6.4 Exercise 8
Section 4.6.4: Evaluation of Polynomials Exercise 8. [ M20 ] The factorial power $x^{\underline{k}}$ is defined to be $k!\binom{x}{k} = x(x-1)\ldots(x-k+1)$. Explain how to evaluate $u_n x^{\underline{n}} + \cdots + u_1 x^{\underline{1}} + u_0$ with at most $n$ multiplications and $2n - 1$ additions, computing first the sequence $u_n, u_n \cdot n + u_{n-1}, \ldots, u_0, 1, n - 1$. Verified: yes Solve time: 4m25s Let $$ P(x)=u_nx^{\underline n}+u_{n-1}x^{\underline{n-1}}+\cdots+u_1x^{\underline1}+u_0, $$...
TAOCP 4.6.4 Exercise 7
Section 4.6.4: Evaluation of Polynomials Exercise 7. [ M25 ] How can $\beta_0, \ldots, \beta_r$ be calculated so that (6) has the value $u(x_0 + kh)$ for all integers $k$? Verified: yes Solve time: 1m09s Solution We wish to compute $\beta_0, \ldots, \beta_r$ so that the polynomial $u(x_0 + kh) = \beta_0 + \beta_1 k + \cdots + \beta_r k^r \eqno(6)$ for all integers $k$. The key is to recognize...
TAOCP 4.6.4 Exercise 4
Section 4.6.4: Evaluation of Polynomials Exercise 4. [ M20 ] The text shows that scheme (3) is superior to Horner's rule when we are evaluating a polynomial with real coefficients at a complex point $z$. Compare (3) to Horner's rule when both the coefficients and the variable $z$ are complex numbers; how many (real) multiplications and addition-subtractions are required by each method? Verified: no Solve time: 4m06s Solution Let $$...
TAOCP 4.6.4 Exercise 2
Section 4.6.4: Evaluation of Polynomials Exercise 2. ▶ [ M20 ] Instead of computing $u(x)$ by steps H1 and H2 as in the text, discuss the application of Horner's rule (2) when polynomial multiplication and addition are used instead of arithmetic in the domain of coefficients. Verified: yes Solve time: 1m13s Solution Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_1 x + u_0$ be a polynomial...
TAOCP 4.6.2 Exercise 33
Section 4.6.2: Factorization of Polynomials Exercise 33. [ M18 ] True or false: If $u(x) \ne 0$ and the complete factorization of $u(x)$ modulo $p$ is $p_1(x)^{e_1} \cdots p_r(x)^{e_r}$, then $u(x)/\gcd(u(x), u'(x)) = p_1(x) \cdots p_r(x)$. Verified: yes Solve time: 1m20s Solution The statement is false. Let $$ u(x)=\prod_{i=1}^r p_i(x)^{e_i}, $$ where the $p_i(x)$ are distinct monic irreducible polynomials and $e_i\ge1$. By differentiating, $$ u'(x) = \sum_{i=1}^r e_i,p_i(x)^{e_i-1}p_i'(x) \prod_{j\ne i}...
TAOCP 4.6.3 Exercise 27
Section 4.6.3: Evaluation of Powers Exercise 27. [ M23 ] (A. Flammenkamp.) What is the smallest $n$ for which every addition chain contains at least eight small steps? Verified: no Solve time: 4m31s Solution Let $$ 1 = a_0 < a_1 < \cdots < a_r = n $$ be an addition chain. Recall Knuth's definitions: $$ \lambda(m) = \lfloor \log_2 m \rfloor . $$ A step $i$ in an addition...
TAOCP 4.6.3 Exercise 26
Section 4.6.3: Evaluation of Powers Exercise 26. ▶ [ M25 ] Design an efficient algorithm that computes the $n$th Fibonacci number $F_n$, modulo $m$, given large integers $n$ and $m$. Verified: yes Solve time: 1m31s Solution We wish to compute the $n$th Fibonacci number $F_n$ modulo $m$, where $n$ and $m$ are large integers. A naive approach, iterating the recurrence $F_0 = 0$, $F_1 = 1$, $F_k = F_{k-1} +...
TAOCP 4.6.3 Exercise 24
Section 4.6.3: Evaluation of Powers Exercise 24. ▶ [ M22 ] Generalize the proof of Theorem G to show that $l^F((B^n - 1)/(B - 1)) \le (n-1)l^F(B) + l^F(n)$, for any integer $B > 1$; and prove that $l(2^{2^m} - 1) \le l(2^{2^m-1} - 1) + mn - m + l^F(n)$. Verified: no Solve time: 4m38s Solution Let $$ R_n(B) = \frac{B^n-1}{B-1} = 1 + B + B^2 + \cdots...
TAOCP 4.6.3 Exercise 23
Section 4.6.3: Evaluation of Powers Exercise 23. [ M20 ] Prove Brauer's inequality (50). Verified: no Solve time: 4m57s Solution Let $$ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \quad p_1 < p_2 < \cdots < p_k $$ be the prime factorization of the positive integer $n$. Brauer's inequality (50) asserts that the minimal length $l(n)$ of an addition chain for $n$ satisfies $$ l(n) \le \alpha_1 + \alpha_2 + \cdots...
TAOCP 4.6.3 Exercise 20
Section 4.6.3: Evaluation of Powers Exercise 20. [ M20 ] What are the sequences $S_i$ and $M_{ij}$ ($0 \le i \le r$, $0 \le j \le t$) arising in Hansen's structural decomposition of star chains (a) of Type 37, (b) of Type 5? (The six "types" are defined in the proof of Theorem B.) Verified: yes Solve time: 5m44s Solution We follow Hansen's structural decomposition of star chains as defined...
TAOCP 4.6.3 Exercise 19
Section 4.6.3: Evaluation of Powers Exercise 19. [ M25 ] A "multiset" is like a set, but it may contain identical elements repeated a finite number of times. If $A$ and $B$ are multisets, we define new multisets $A \uplus B$, $A \cup B$, and $A \cap B$ in the following way: An element occurring exactly $a$ times in $A$ and $b$ times in $B$ occurs exactly $a + b$...
TAOCP 4.6.3 Exercise 17
Section 4.6.3: Evaluation of Powers Exercise 17. [ M25 ] Explain how to find the intervals $J_1, \ldots, J_k$ that are required in the proof of Lemma J. Verified: no Solve time: 2m18s Solution In the proof of Lemma J, the intervals $J_1,\ldots,J_k$ are introduced in order to partition a finite set of admissible values into maximal consecutive blocks. Let $S$ denote the set of integers that satisfy the condition...
TAOCP 4.6.3 Exercise 13
Section 4.6.3: Evaluation of Powers Exercise 13. [ M21 ] Find a star chain of length $A + 2$ for each of the four cases listed in Theorem C. (Consequently Theorem C holds also with $l$ replaced by $l^*$.) Verified: yes Solve time: 1m57s Solution We are asked to construct a star chain of length $A+2$ for each of the four cases in Theorem C, thereby showing that Theorem C...
TAOCP 4.6.3 Exercise 8
Section 4.6.3: Evaluation of Powers Exercise 8. [ M21 ] Prove that the power tree (exercise 5) never gives more multiplications for the computation of $x^n$ than the binary method. Verified: yes Solve time: 3m43s Solution Let $b(n)$ denote the number of multiplications used by the left-to-right binary method to compute $x^n$. If the binary representation of $n$ has length $k+1$, then $$ b(n) = k + \nu(n) - 1,...
TAOCP 4.6.3 Exercise 7
Section 4.6.3: Evaluation of Powers Exercise 7. [ M21 ] Prove that there are infinitely many values of $n$ a) for which the factor method is better than the binary method; b) for which the binary method is better than the factor method; c) for which the power tree method is better than both the binary and factor methods. (Here the "better" method is the one that computes $x^n$ using...
TAOCP 4.6.2 Exercise 40
Section 4.6.2: Factorization of Polynomials Exercise 40. ▶ [ M20 ] (P. S. Wang.) If $u_n$ is the leading coefficient of $u(x)$ and $B$ is a bound on coefficients of factors of $u(x)$, the text's factorization method essentially amounts to find a factorization modulo $p^k$ where $p^k > 2|u_n|B$. Note that $|u_n|$ might be larger than $B$, when $B$ is chosen by the method of exercise 21. Show that if...
TAOCP 4.6.2 Exercise 36
Section 4.6.2: Factorization of Polynomials Exercise 36. [ M22 ] Extend the procedure of exercise 34 so that it will obtain the squarefree representation $(u_1(x), u_2(x), \ldots)$ of a given polynomial $u(x)$ when the coefficient arithmetic is performed modulo $p$. Verified: yes Solve time: 2m33s Solution Let $$ u(x)=\prod_{i\ge1} u_i(x)^i $$ be the squarefree representation of the given polynomial modulo $p$. The difficulty, compared with Exercise 34, is that the...
TAOCP 4.6.2 Exercise 35
Section 4.6.2: Factorization of Polynomials Exercise 35. [ M22 ] (D. Y. Y. Yun.) Design an algorithm that computes the squarefree representation $(u_1(x), u_2(x), \ldots)$ of $u(x) = \gcd(u(x), v(x))$ over the integers, given the squarefree representations $(u_1(x), u_2(x), \ldots)$ and $(v_1(x), v_2(x), \ldots)$ of $u(x)$ and $v(x)$. Verified: yes Solve time: 2m53s Solution Let $$ u(x)=u_1(x)u_2(x)^2u_3(x)^3\cdots u_e(x)^e, $$ where the $u_i(x)$ are squarefree and pairwise relatively prime, and where...
TAOCP 4.6.2 Exercise 34
Section 4.6.2: Factorization of Polynomials Exercise 34. ▶ [ M25 ] (Squarefree factorization.) It is clear that any primitive polynomial of a unique factorization domain can be expressed in the form $u(x) = u_1(x)u_2(x)^2u_3(x)^3\ldots$, where the polynomials $u_i(x)$ are squarefree and relatively prime to each other. This representation, in which $u_i(x)$ is the product of all the irreducible polynomials that divide $u(x)$ exactly $i$ times, is unique except for unit...
TAOCP 4.6.2 Exercise 22
Section 4.6.2: Factorization of Polynomials Exercise 22. ▶ [ M24 ] (Hensel's Lemma.) Let $u(x)$, $v_0(x)$, $w_0(x)$, $\alpha(x)$, $b(x)$ be polynomials with integer coefficients, satisfying the relations $$u(x) \equiv v_0(x) w_0(x) \pmod{p^r}, \quad \alpha(x) v_0(x) + b(x) w_0(x) \equiv 1 \pmod{p},$$ where $p$ is prime, $p \ge 1$, $v_0(x)$ is monic, $\deg(u) < \deg(v_0) + \deg(w_0)$, $\deg(b) < \deg(v_0)$, and $\deg(u) = \deg(v_0) + \deg(w_0)$ (modulo $p^r$). Show how to...
TAOCP 4.6.2 Exercise 18
Section 4.6.2: Factorization of Polynomials Exercise 18. ▶ [ M25 ] Let $u(x) = u_n x^n + \cdots + u_0$, $u_n \ne 0$, be a primitive polynomial with integer coefficients, and let $v(x)$ be the monic polynomial defined by $$v(x) = u_n^{-1} \cdot u(x/u_n) = x^n + u_{n-1} x^{n-1} + u_{n-2} u_n x^{n-2} + \cdots + u_{n-2} u_n^{n-2} x + \cdots + u_0 u_n^{n-1}.$$ (a) Given that each $p_i(x)$ is...
TAOCP 4.6.2 Exercise 19
Section 4.6.2: Factorization of Polynomials Exercise 19. [ M20 ] (Eisenstein's criterion.) Perhaps the best-known class of irreducible polynomials over the integers was introduced by T. Schönemann in Crelle 32 (1846), 100, then popularized by G. Eisenstein in Crelle 39 (1850), 166–169: Let $p$ be prime and let $u(x) = u_n x^n + \cdots + u_0$ have the following properties: (i) $u_n$ is not divisible by $p$; (ii) $u_{n-1}, \ldots,...
TAOCP 4.6.2 Exercise 17
Section 4.6.2: Factorization of Polynomials Exercise 17. [ M23 ] Let $F$ be a field with $13^2$ elements. How many elements of $F$ have order $f$, for each integer $f$ with $1 \le f < 13^2$? (The order of an element $a$ is the least positive integer $m$ such that $a^m = 1$.) Verified: yes Solve time: 2m12s Solution Let $F$ be a finite field with $13^2 = 169$ elements....
TAOCP 4.6.2 Exercise 13
Section 4.6.2: Factorization of Polynomials Exercise 13. [ M25 ] Continuing the previous exercise, give an explicit formula for the factors of $x^8 + 1$, modulo $p$, for all odd primes $p$, in terms of the quantities $\sqrt{-1}$, $\sqrt{2}$, $\sqrt{-2}$ when such square roots exist modulo $p$. Verified: no Solve time: 10m01s Solution to Exercise 4.6.2.13 We are asked to give an explicit factorization of $$ x^8 + 1 $$...
TAOCP 4.6.2 Exercise 6
Section 4.6.2: Factorization of Polynomials Exercise 6. [ M21 ] (J. L. Lagrange, 1771.) Prove the congruence (9). [ Hint: Factor $x^p - x$ in the field of $p$ elements.] Verified: yes Solve time: 3m35s Solution We are asked to prove the congruence $$ x^p - x \equiv (x-0)(x-1)\cdots(x-(p-1)) \pmod{p}, \eqno(9) $$ where $p$ is a prime and arithmetic is in the field $\mathbb{F}_p$ of $p$ elements. Let $$ f(x)...
TAOCP 4.6.2 Exercise 3
Section 4.6.2: Factorization of Polynomials Exercise 3. [ M25 ] ( The Chinese remainder theorem for polynomials. ) Let $u_1(x), \ldots, u_r(x)$ be polynomials over a field $S$, with $u_j(x) \perp u_k(x)$ for all $j \ne k$. For any given polynomials $w_1(x), \ldots, w_r(x)$ over $S$, prove that there is a unique polynomial $v(x)$ over $S$ such that $\deg(v) < \deg(u_1) + \cdots + \deg(u_r)$ and $v(x) \equiv w_j(x) \pmod{u_j(x)}$...
TAOCP 4.6.2 Exercise 2
Section 4.6.2: Factorization of Polynomials Exercise 2. ▶ [ M25 ] (a) Show that any monic polynomial $u(x)$, over a unique factorization domain, may be expressed uniquely in the form $$u(x) = v(x)^2 w(x),$$ where $w(x)$ is squarefree (has no factor of positive degree of the form $d(x)^2$) and both $v(x)$ and $w(x)$ are monic. (b) (E. R. Berlekamp.) How many monic polynomials of degree $n$ are squarefree modulo $p$,...
TAOCP 4.6.2 Exercise 1
Section 4.6.2: Factorization of Polynomials Exercise 1. ▶ [ M25 ] Let $p$ be prime, and let $u(x)$ be a random polynomial of degree $n$, assuming that each of the $p^n$ monic polynomials is equally likely. Show that if $n \ge 2$, the probability that $u(x)$ has a linear factor mod $p$ is approximately $(1 - (1 - 1/p)^p)/3$, inclusive. Give a closed form for this probability when $n \ge...
TAOCP 4.6.1 Exercise 23
Section 4.6.1: Division of Polynomials Exercise 23. [ M22 ] Prove that if $u(x)$ in (29) has $\deg(u)$ real roots, then we have $\deg(u_{j+1}) = \deg(u_j) - 1$ for $0 \le j \le k$. Verified: no Solve time: 4m57s Solution Let $u(x),v(x)\in\mathbf{R}[x]$ be polynomials whose coefficients are represented in floating-point arithmetic. The exercise asks us to investigate the behavior of Euclid's algorithm in this context, and to describe the notion...
TAOCP 4.6.1 Exercise 21
Section 4.6.1: Division of Polynomials Exercise 21. [ M25 ] Prove that the computation time required by Algorithm C to compute the gcd of two $n$th degree polynomials over the integers is $O(n^4(\log Nn)^2)$, if the coefficients of the given polynomials are bounded by $N$ in absolute value. Verified: yes Solve time: 5m24s Solution Let the input polynomials be $$ u_0(x),\qquad u_1(x), $$ with $$ \deg u_0 = \deg u_1...
TAOCP 4.6.1 Exercise 22
Section 4.6.1: Division of Polynomials Exercise 22. [ M23 ] Prove Sturm's theorem. [ Hint: Some sign sequences are impossible.] Verified: yes Solve time: 2m05s Solution Let $f_0(x),f_1(x),\ldots,f_m(x)$ be the Sturm sequence associated with a squarefree polynomial $f_0(x)$, defined by $f_{i-1}(x)=q_i(x)f_i(x)-f_{i+1}(x)\qquad(1\le i<m),$ where $f_m(x)$ is a nonzero constant and where each $f_{i+1}(x)$ is the negative of the remainder obtained when $f_{i-1}(x)$ is divided by $f_i(x)$. For any real number $t$...
TAOCP 4.6.1 Exercise 13
Section 4.6.1: Division of Polynomials Exercise 13. [ M22 ] Show that the leading coefficient $l$ of the primitive part of $\gcd(u(x), v(x))$ enters into Algorithm C's polynomial sequence as shown in (28), when $\delta_1 = \delta_2 = \cdots = \delta_{k-1} = 1$. What is the behavior for general $\delta_j$? Verified: no Solve time: 9m47s Solution Let $S$ be a unique factorization domain, and let $u(x),v(x)\in S[x]$. Consider the polynomial...
TAOCP 4.6.1 Exercise 16
Section 4.6.1: Division of Polynomials Exercise 16. ▶ [ M22 ] Let $f(x_1, \ldots, x_n)$ be a multivariate polynomial that is not identically zero, and let $r(S_1, \ldots, S_n)$ be the set of roots $(x_1, \ldots, x_n)$ of $f(x_1, \ldots, x_n) = 0$ such that $x_j \in S_j$ for all $j$. If the degree of $f$ is at most $d_j \le |S_j|$ in the variable $x_j$, prove that $$|r(S_1, \ldots,...
TAOCP 4.6.1 Exercise 14
Section 4.6.1: Division of Polynomials Exercise 14. [ M23 ] Let $r(x)$ be the pseudo-remainder when $u(x)$ is pseudo-divided by $v(x)$. If $\deg(u) \ge \deg(v) + 2$ and $\deg(u) \ge \deg(v) + 2$, show that $r(x)$ is a multiple of $l(v)$. Verified: yes Solve time: 4m16s Solution Let $$ u(x)=u_mx^m+\cdots,\qquad v(x)=ax^n+\cdots, $$ where $a=l(v)$, and let $m=\deg(u)$, $n=\deg(v)$. Assume that $$ m\ge n+2. $$ Recall the pseudo-division algorithm. Starting with...
TAOCP 4.6.1 Exercise 12
Section 4.6.1: Division of Polynomials Exercise 12. ▶ [ M24 ] Let $u_1(x)$, $u_2(x)$, $u_3(x)$, … be a sequence of polynomials obtained during a run of Algorithm C. "Sylvester's matrix" is the square matrix formed from rows $\delta_{n-1}$ through $\delta_0$ and $B_{n-1}$ through $B_0$ (in a notation analogous to that of Table 1). Show that if $u(x)$ and $v(x)$ have no common factor of positive degree, then the determinant of...
TAOCP 4.6.1 Exercise 9
Section 4.6.1: Division of Polynomials Exercise 9. [ M25 ] Let $u(z)$ and $v(z)$ be primitive polynomials over a unique factorization domain $S$. Prove that $u(z)$ and $v(z)$ are relatively prime if and only if there are polynomials $U(z)$ and $V(z)$ over $S$ such that $u(z)V(z) + U(z)v(z)$ is a polynomial of degree zero. [ Hint: Extend Algorithm E , as Algorithm 4.5.2A is extended in exercise 3.] Verified: yes...
TAOCP 4.6.1 Exercise 11
Section 4.6.1: Division of Polynomials Exercise 11. [ M22 ] What row names would have appeared in Table 1 if the sequence of degrees had been 9, 6, 5, 2, $-\infty$ instead of 8, 6, 4, 2, 1, 0? Verified: yes Solve time: 4m17s Solution Table 1 in Section 4.6.1 records the steps of Algorithm D (division of polynomials) and, in particular, the row names , which correspond to the...
TAOCP 4.6.1 Exercise 3
Section 4.6.1: Division of Polynomials Exercise 3. ▶ [ M25 ] Show that Euclid's algorithm for polynomials over a field $S$ can be extended to find polynomials $U(x)$ and $V(x)$ over $S$ such that $$u(x)V(x) + U(x)v(x) = \gcd(u(x), v(x)).$$ (See Algorithm 4.5.2X.) What are the degrees of the polynomials $U(x)$ and $V(x)$ that are computed by this extended algorithm? Prove that if $S$ is the field of rational numbers,...
TAOCP 4.6.1 Exercise 8
Section 4.6.1: Division of Polynomials Exercise 8. ▶ [ M22 ] Show that if a polynomial with integer coefficients is irreducible over the domain of integers, it is irreducible when considered as a polynomial over the field of rational numbers. Verified: no Solve time: 1m28s Solution Let $f(x)$ be a polynomial with integer coefficients. Assume that $f(x)$ is irreducible over the domain of integers. We shall prove that $f(x)$ is...
TAOCP 4.6.1 Exercise 5
Section 4.6.1: Division of Polynomials Exercise 5. [ M22 ] What is the probability that $u(x)$ and $v(x)$ are relatively prime modulo $p$, if $u(x)$ and $v(x)$ are independently and uniformly distributed monic polynomials of degree $n$? Verified: yes Solve time: 4m23s Solution Let $P_n=\Pr\bigl(\gcd(u(x),v(x))=1\bigr),$ where $u(x)$ and $v(x)$ are independently and uniformly distributed monic polynomials of degree $n$ over the field $\mathbf F_p$. We shall determine $P_n$ exactly. Fix...
TAOCP 4.6 Exercise 5
Section 4.6: Polynomial Arithmetic Exercise 5. ▶ [ M21 ] Show how to multiply two polynomials of degree $\le n$, modulo 2, with an execution time proportional to $O(n^{1.5})$ when $n$ is large, by adapting Karatsuba's method (see Section 4.3.3). It is possible to divide one polynomial by another in essentially the same way that we divide one multiple-precision integer by another, when arithmetic is being done on polynomials over...
TAOCP 4.6 Exercise 3
Section 4.6: Polynomial Arithmetic Exercise 3. [ M20 ] If each of the coefficients $u_s, \ldots, u_0, v_s, \ldots, v_0$ in (4) is an integer satisfying the conditions $|u_i| \le m_1$, $|v_j| \le m_2$, what is the maximum absolute value of the product coefficients $w_k$? Verified: yes Solve time: 1m09s Solution By equation (4), $$ w_k=u_0v_k+u_1v_{k-1}+\cdots+u_kv_0, $$ where coefficients with indices exceeding $s$ are taken to be $0$. Since both...
TAOCP 4.5.4 Exercise 35
Section 4.5.4: Factoring into Primes Exercise 35. ▶ [ M25 ] (H. C. Williams, 1979.) Let $N$ be the product of two primes $p$ and $q$, where $p \bmod 8 = 3$ and $q \bmod 8 = 7$. Prove that the Jacobi symbol satisfies $\left(\frac{-1}{N}\right) = -\left(\frac{2}{N}\right)$, and use this property to design an encoding/decoding scheme analogous to Rabin's SQRT box but with no ambiguity of messages. Verified: yes Solve...
TAOCP 4.5.4 Exercise 32
Section 4.5.4: Factoring into Primes Exercise 32. ▶ [ M21 ] Show how to modify the RSA encoding scheme so that there is no problem with messages $< \sqrt[3]{N}$, in such a way that the length of messages is not substantially increased. Verified: yes Solve time: 5m40s Solution In textbook RSA, a message $M$ is encoded as $$ C \equiv M^3 \pmod N, $$ where $N=pq$ and the public exponent...
TAOCP 4.5.4 Exercise 31
Section 4.5.4: Factoring into Primes Exercise 31. [ M20 ] Use exercise 1.2.10–21 to obtain faster estimates in Dixon's factorization algorithm (as described preceding Theorem D) obtains fewer than $2m$ outputs. Verified: no Solve time: 5m34s Solution Let $P_k$ denote the probability that the first $k$ parity vectors produced by Dixon's algorithm are linearly independent in $GF(2)^m$, under the usual heuristic assumption that the vectors are independent random elements of...
TAOCP 4.5.4 Exercise 19
Section 4.5.4: Factoring into Primes Exercise 19. ▶ [ M25 ] (J. M. Pollard.) Show how to compute a number $M$ that is divisible by all odd primes $p$ such that $p - 1$ is a divisor of some given number $D$. [ Hint: Consider numbers of the form $a^k - 1$.] Such an $M$ is useful in factorization, for by computing $\gcd(M, N)$ we may find prime factors of...
TAOCP 4.5.4 Exercise 17
Section 4.5.4: Factoring into Primes Exercise 17. [ M25 ] (V. R. Pratt.) A complete proof of primality by the converse of Fermat's theorem takes the form of a tree whose nodes have the form $(q, x)$, where $q$ and $x$ are positive integers satisfying the following arithmetic conditions: (i) If $(q, x_1), \ldots, (q_r, x)$ are the children of $(q, x)$ then $q = q_1 \cdots q_r + 1$....
TAOCP 4.5.4 Exercise 14
Section 4.5.4: Factoring into Primes Exercise 14. [ M20 ] Prove that the number $T$ in step E3 of Algorithm E will never be a multiple of an odd prime $p$ for which $(kN)^{(p-1)/2} \bmod p > 1$. Verified: yes Solve time: 5m52s Solution Let $T$ be the integer formed in step E3 of Algorithm E. The crucial fact is the condition imposed on $x$ in step E2: $$ x^{2}\equiv...
TAOCP 4.5.4 Exercise 11
Section 4.5.4: Factoring into Primes Exercise 11. [ M20 ] What outputs does Algorithm E give when $N = 197209$, $k = 5$, $m = 1$? [Hint: $\sqrt{5 \cdot 197209} \approx 992 + \frac{1}{1.495}, \frac{1}{2.495}, \frac{1}{2.495}, \frac{1}{1.984} \cdots]$ Verified: yes Solve time: 3m01s Solution Algorithm E is the continued-fraction factoring method applied to $\sqrt{kN}$. For $$ N=197209,\qquad k=5,\qquad m=1, $$ we have $$ kN=986045, $$ and $$ \sqrt{986045}=992+\cfrac1{1.495\ldots} =992+\cfrac1{1+\cfrac1{2.495\ldots}} =...
TAOCP 4.5.4 Exercise 9
Section 4.5.4: Factoring into Primes Exercise 9. [ M25 ] Let $n$ be an odd number, $n \ge 3$. Show that if the number $\lambda(n)$ of Theorem 3.2.1.2B is a divisor of $n - 1$ but not equal to $n - 1$, then $n$ must have the form $p_1 p_2 \ldots p_r$ where the $p$'s are distinct primes and $r \ge 3$. Verified: yes Solve time: 2m28s Solution Let $n$...
TAOCP 4.5.4 Exercise 6
Section 4.5.4: Factoring into Primes Exercise 6. [ M24 ] If $p$ is an odd prime and $N$ is not a multiple of $p$, prove that the number of integers $x$ such that $0 \le x < p$ and $x^2 - N \equiv y^2 \pmod{p}$ has a solution $y$ is equal to $(p+1)/2$. Verified: no Solve time: 7m20s Solution Let $p$ be an odd prime, and let $N$ be an...
TAOCP 4.5.4 Exercise 3
Section 4.5.4: Factoring into Primes Exercise 3. [ M20 ] Show that there is a number $P$ with the following property: If $1000 \le n \le 1000000$, then $n$ is prime if and only if $\gcd(n, P) = 1$. Verified: yes Solve time: 7m54s Solution Let $$ P=\prod_{p\le 1000} p, $$ where the product extends over all prime numbers not exceeding $1000$. We shall prove that for every integer $n$...
TAOCP 4.5.3 Exercise 39
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 39. ▶ [ M25 ] (R. W. Gosper.) If a baseball player's batting average is $.334$, what is the smallest possible number of times he has been at bat? [Note for non-baseball-fans: Batting average $=$ (number of hits)/(times at bat), rounded to three decimal places.] Verified: yes Solve time: 4m37s Solution Let $h$ be the number of hits and $n$ the number of...
TAOCP 4.5.3 Exercise 36
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 36. [ M25 ] (G. H. Bradley.) What is the smallest value of $u_n$ such that the calculation of $\gcd(u_1, \ldots, u_n)$ by Algorithm 4.5.2C requires $N$ divisions, if Euclid's algorithm is used throughout? Assume that $N \ge n \ge 3$. Verified: no Solve time: 8m12s Solution We are asked: What is the smallest value of $u_n$ such that the calculation of $\gcd(u_1,...
TAOCP 4.5.3 Exercise 29
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 29. [ M23 ] Assuming that $T_n$ is shown by (55), show that (57) equals (58). Verified: yes Solve time: 5m57s Solution A rigorous proof cannot be supplied from the information given. Exercise 4.5.3.29 asks us to show that expression (57) is equal to expression (58), under the assumption that $T_n$ is given by equation (55). Any valid solution must therefore: Write down...
TAOCP 4.5.3 Exercise 28
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 28. [ M23 ] Prove the following identities involving the three number-theoretic functions $\varphi(n)$, $\mu(n)$, $\Lambda(n)$: $$\text{a)};\sum_{d|n} \mu(d) = \delta_{n1}, \qquad \text{b)};\ln n = \sum_{d|n} \Lambda(d), \qquad n = \sum_{d|n} \varphi(d).$$ $$\text{c)};\Lambda(n) = \sum_{d|n} \mu!\left(\frac{n}{d}\right)\ln d, \qquad \varphi(n) = \sum_{d|n} \mu!\left(\frac{n}{d}\right) d.$$ Verified: yes Solve time: 1m29s Solution Let $1(n)$ denote the constant function $1$, and let $\delta_{n1}$ be $1$ when $n=1$ and...
TAOCP 4.5.3 Exercise 27
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 27. [ M21 ] Prove (55) from (43) and (54). Verified: yes Solve time: 5m05s Let $$ S(M,N)=\sum_{m\le M}\sum_{n\le N}T(m,n). $$ Since Euclid's algorithm is unchanged when its arguments are interchanged, $$ T(m,n)=T(n,m). $$ Hence $S(M,N)=S(N,M)$. It therefore suffices to prove (55) under the assumption $$ M\le N. $$ Then $\min(M,N)=M$, and we must show that $$ S(M,N)=\frac{12}{\pi^2}MN\ln M+O(MN). $$ Equation (54) states...
TAOCP 4.5.3 Exercise 26
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 26. [ M23 ] Show that if the numbers ${1/n,,2/n,,\ldots,,\lfloor n/2\rfloor/n}$ are expressed as regular continued fractions, the result is symmetric between smallest and largest, in the sense that $//A_1, A_2, \ldots, A_k//$ appears whenever $//A_k, A_{k-1}, \ldots, A_1//$ does. Verified: no Solve time: 4m08s Exercise 4.5.3.26 [ M23 ] Show that if the numbers $$ \left{\frac{1}{n}, \frac{2}{n}, \ldots, \frac{\lfloor n/2 \rfloor}{n}\right} $$...
TAOCP 4.5.3 Exercise 24
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 24. [ M22 ] What is the average value of a partial quotient $A_n$ in the regular continued fraction expansion of a random real number? Verified: yes Solve time: 2m26s Let $A_n$ denote the $n$th partial quotient in the regular continued fraction expansion of a random real number $x\in(0,1)$, $$ x=[0;A_1,A_2,\ldots]. $$ For a random real number, the distribution of the partial quotients...
TAOCP 4.5.3 Exercise 19
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 19. [ M20 ] Prove $F(x) = \log_2(1 + x)$ satisfies Eq. (24). Verified: no Solve time: 1m50s Solution Equation (24) is $$ F(x)=\sum_{k\ge1}\left(F!\left(\frac1k\right)-F!\left(\frac1{k+x}\right)\right), \qquad 0\le x\le1. $$ Let $$ F(x)=\log_2(1+x). $$ Then $$ F!\left(\frac1k\right)-F!\left(\frac1{k+x}\right) = \log_2!\left(\frac{k+1}{k}\right) - \log_2!\left(\frac{k+x+1}{k+x}\right), $$ hence $$ F!\left(\frac1k\right)-F!\left(\frac1{k+x}\right) = \log_2!\left( \frac{(k+1)(k+x)} {k(k+x+1)} \right). $$ Therefore the partial sums of the right-hand side of (24) are $$ S_N =...
TAOCP 4.5.3 Exercise 17
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 17. ▶ [ M23 ] (a) Prove that $//x_1, -x_2// = //x_1 - 1, x_2 - 1, 1//$. (b) Generalize this identity, obtaining a formula for $//x_1, -x_2, x_3, -x_4, x_5, -x_6, \ldots//$ in which all partial quotients are positive integers when the $x$'s are large positive integers. (c) The result of exercise 16 implies that $\tan 1 = //1, -3, 5, -7,...
TAOCP 4.5.3 Exercise 14
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 14. [ M22 ] (A. Hurwitz, 1891.) Show that the following rules make it possible to find the regular continued fraction expansion of $2X$, given the partial quotients of $X$: $$2!/!/ 2a, b, c, \ldots /!/ = /!/ a, 2b + 2/!/b, c, \ldots /!/;$$ $$2!/!/ 2a, 1, b, c, \ldots /!/ = /!/ a, 1, 2/!/1, b, c, \ldots /!/.$$ Use this...
TAOCP 4.5.3 Exercise 4
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 4. [ M20 ] Prove Eq. (8). Verified: yes Solve time: 41m25s Solution Let $$ D_n= K_n(x_1,\ldots,x_n),K_n(x_2,\ldots,x_{n+1}) - K_{n+1}(x_1,\ldots,x_{n+1}),K_{n-1}(x_2,\ldots,x_n). $$ Equation (8) asserts that $$ D_n=(-1)^n \qquad (n\ge1). $$ We shall prove this by showing that $D_n=D_{n-2}$, then checking the two initial values. Recall the continuant recurrence $$ K_n(x_1,\ldots,x_n) = x_nK_{n-1}(x_1,\ldots,x_{n-1}) + K_{n-2}(x_1,\ldots,x_{n-2}), $$ valid for $n\ge2$, together with $K_0=1$ and $K_1(x)=x$. Initial...
TAOCP 4.5.3 Exercise 3
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 3. [ M21 ] What is the value of $\det\begin{pmatrix} x_1 & 1 & 0 & \cdots & 0 \ -1 & x_2 & 1 & & \vdots \ 0 & -1 & x_3 & 1 & \ \vdots & & -1 & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix}$? Verified: yes Solve time: 1m30s Solution...
TAOCP 4.5.3 Exercise 2
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 2. [ M21 ] Evaluate the matrix product $\begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix}\begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix}\cdots\begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix}$. Verified: yes Solve time: 32m23s Solution Let us consider the product $M_n = \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix}x_2 & 1 \ 1 & 0\end{pmatrix} \cdots \begin{pmatrix}x_n...
TAOCP 4.5.2 Exercise 41
Section 4.5.2: The Greatest Common Divisor Exercise 41. [ M22 ] Use Euclid's algorithm to find a simple formula for $\gcd(10^m - 1, 10^n - 1)$ when $m$ and $n$ are nonnegative integers. Verified: yes Solve time: 23m47s Solution Let $$ G(m,n)=\gcd(10^m-1,;10^n-1), $$ where $m,n\ge 0$. We first treat the case in which one exponent is $0$. If $n=0$, then $$ 10^0-1=0, $$ so $$ G(m,0)=\gcd(10^m-1,0)=10^m-1. $$ Since $\gcd(m,0)=m$, this...
TAOCP 4.5.2 Exercise 40
Section 4.5.2: The Greatest Common Divisor Exercise 40. ▶ [ M25 ] (R. P. Brent and H. T. Kung.) The following variant of the binary gcd algorithm is better than Algorithm B from the standpoint of hardware implementation, because it does not require testing the sign of $u - v$. Assume that $u$ is odd; $u$ and $v$ can be either positive or negative. K1. [Initialize.] Set $c \leftarrow 0$....
TAOCP 4.5.2 Exercise 6
Section 4.5.2: The Greatest Common Divisor Exercise 6. [ M22 ] Given that $u$ and $v$ are random positive integers, find the mean and the standard deviation of the quantity $A$ that enters into the timing of Program B. (This is the number of right shifts applied to both $u$ and $v$ during the preparatory phase.) Verified: yes Solve time: 4m59s Solution Let $u$ and $v$ be random positive integers....
TAOCP 4.5.2 Exercise 7
Section 4.5.2: The Greatest Common Divisor Exercise 7. [ M20 ] Analyze the quantity $B$ that enters into the timing of Program B. Verified: yes Solve time: 2m35s Solution In Program B of §4.5.2, the binary gcd algorithm computes $\gcd(u, v)$ of two nonnegative integers $u$ and $v$ using only shifts, comparisons, and subtractions. The timing of Program B is expressed in terms of several quantities, among which $B$ is...
TAOCP 4.5.2 Exercise 4
Section 4.5.2: The Greatest Common Divisor Exercise 4. [ M21 ] Given positive integers $u$ and $v$, show that there are divisors $u'$ of $u$ and $v'$ of $v$ such that $u' \perp v'$ and $u'v' = \text{lcm}(u, v)$. Verified: yes Solve time: 4m02s Solution Let $u$ and $v$ be positive integers. Write their canonical prime factorizations as $$ u = \prod_{p\text{ prime}} p^{u_p}, \qquad v = \prod_{p\text{ prime}} p^{v_p},...
TAOCP 4.5.2 Exercise 1
Section 4.5.2: The Greatest Common Divisor Exercise 1. [ M21 ] How can (8), (9), (10), (11), and (12) be derived easily from (6) and (7)? Verified: yes Solve time: 3m04s Solution We derive equations (8) through (12) from the prime-factor definitions (6) and (7). Let $u$, $v$, and $w$ be nonnegative integers, with canonical prime factorizations $$ u = \prod_{p \text{ prime}} p^{u_p}, \quad v = \prod_{p \text{ prime}}...
TAOCP 4.5.2 Exercise 3
Section 4.5.2: The Greatest Common Divisor Exercise 3. [ M23 ] Show that the number of ordered pairs of positive integers $(u, v)$ such that $\text{lcm}(u, v) = n$ is the number of divisors of $n^2$. Verified: yes Solve time: 1m15s Solution Let $$ n=\prod_{p}p^{a_p} $$ be the canonical factorization of $n$, as in (5), where only finitely many exponents $a_p$ are nonzero. Suppose that $$ u=\prod_{p}p^{b_p}, \qquad v=\prod_{p}p^{c_p}, $$...
TAOCP 4.5.2 Exercise 2
Section 4.5.2: The Greatest Common Divisor Exercise 2. [ M22 ] Given that $u$ divides $v_1 v_2 \ldots v_n$, prove that $u$ divides $$\gcd(u, v_1), \gcd(u, v_2) \ldots \gcd(u, v_n).$$ Verified: yes Solve time: 1m15s Solution Let $$ u=\prod_{p} p^{u_p}, \qquad v_i=\prod_{p} p^{v_{i,p}} \quad (1\le i\le n) $$ be the canonical prime factorizations of the positive integers involved, as in equation (5). Since $$ u\mid v_1v_2\cdots v_n, $$ comparison of...
TAOCP 4.4 Exercise 19
Section 4.4: Radix Conversion Exercise 19. ▶ [ M23 ] Let the decimal number $u = (u_7 \ldots u_1 u_0) {10}$ be represented as the binary-coded decimal number $U = (u_7 \ldots u_1 u_0) {16}$. Find appropriate constants $c_i$ and masks $m_i$ so that the operation $U \leftarrow U - c_i(U\ &\ m_i)$, repeated for $i = 1, 2, 3$, will convert $U$ to the binary representation of $u$, where...
TAOCP 4.4 Exercise 7
Section 4.4: Radix Conversion Exercise 7. [ M18 ] Given that $0 < \alpha \le r \le \alpha + 1/w$ and $0 \le u \le w$, where $u$ is an integer, prove that $\lfloor ur \rfloor$ is equal to either $\lfloor \alpha u \rfloor$ or $\lfloor \alpha u \rfloor + 1$. Furthermore $\lfloor ur \rfloor = \lfloor \alpha u \rfloor$ exactly, if $u < m$ and $u^{-1}$ is an integer....
TAOCP 4.4 Exercise 4
Section 4.4: Radix Conversion Exercise 4. [ M21 ] (a) Prove that every real number with a terminating binary representation also has a terminating decimal representation. (b) Find a simple condition on the positive integers $b$ and $B$ that is satisfied if and only if every real number that has a terminating radix-$b$ representation also has a terminating radix-$B$ representation. Verified: yes Solve time: 2m49s Solution (a) Let $x$ be...
TAOCP 4.3.3 Exercise 19
Section 4.3.3: How Fast Can We Multiply? Exercise 19. ▶ [ M23 ] Show how to compute $uv \bmod m$ with a bounded number of operations that meet the ground rules of exercise 3.2.1.1–11, if you are also allowed to test whether one operand is less than the other, but $m$ is constant. Hint: Consider the decomposition in (2). Verified: yes Solve time: 6m56s Solution We are asked to compute...
TAOCP 4.3.3 Exercise 13
Section 4.3.3: How Fast Can We Multiply? Exercise 13. [ M25 ] What is a good upper bound on the time needed to multiply an $m$-bit number by an $n$-bit number, when both $m$ and $n$ are very large but $n$ is much larger than $m$, based on the results discussed in this section for the case $m = n$? Verified: yes Solve time: 1m16s Solution Let $T(n)$ denote the...
TAOCP 4.3.3 Exercise 8
Section 4.3.3: How Fast Can We Multiply? Exercise 8. [ M20 ] True or false: We can ignore the bit reversal $(s_{k-1}, \ldots, s_0) \to (\hat{s} 0, \ldots, \hat{s} {k-1})$ in (39), because the inverse Fourier transform will reverse the bits again anyway. Verified: yes Solve time: 1m24s Solution The assertion that $u_{j+n} = 0$ at the beginning of step D3 of Algorithm D is false. At this point in...
TAOCP 4.3.2 Exercise 33
Section 4.3.2: Modular Arithmetic Exercise 33. ▶ [ M25 ] (Automorphic numbers.) An $n$-digit decimal number $x > 1$ is called an "automorph" by recreational mathematicians if the last $n$ digits of $x^2$ are equal to $x$. For example, $9376$ is a 4-digit automorph, since $9376^2 = 87909376$. [See Scientific American 218 .1 (January 1968), 125.] a) Prove that an integer $x > 1$ is an automorph if and only...
TAOCP 4.3.3 Exercise 6
Section 4.3.3: How Fast Can We Multiply? Exercise 6. [ M23 ] Prove that the six numbers in (24) are relatively prime in pairs. Verified: no Solve time: 4m45s Solution We are asked to prove that the six numbers in equation (24) of Section 4.3.3 are relatively prime in pairs . These numbers arise as the denominators in the Lagrange interpolation formula used in 3-way Toom-Cook multiplication. Step 1: Recall...
TAOCP 4.3.3 Exercise 7
Section 4.3.3: How Fast Can We Multiply? Exercise 7. [ M23 ] Prove (25). Verified: yes Solve time: 2m50s Solution We are asked to show that if in step T1 of Algorithm T we replace the original initialization $R \leftarrow \lfloor \sqrt{Q} \rfloor$ by $R \leftarrow \lceil \sqrt{2Q} \rceil + 1,$ then the bound on the size of the interpolation coefficients, previously stated in equation (20) as $t_k \le q_{k+1}...
TAOCP 4.3.3 Exercise 3
Section 4.3.3: How Fast Can We Multiply? Exercise 3. [ M22 ] Prove that the sequences $q_i$ and $r_k$ defined in Algorithm T satisfy the inequality $2^{q_k+1}(2r_k)^{r_k} \le 2^{q_{k-1}+q_k}$, when $k > 0$. Verified: yes Solve time: 4m34s Solution For $k>0$, the desired inequality is $$ 2^{q_k+1}(2r_k)^{r_k}\le 2^{q_{k-1}+q_k}. $$ Since $2^{q_k}>0$, we may divide both sides by $2^{q_k}$. The statement is therefore equivalent to $$ 2(2r_k)^{r_k}\le 2^{q_{k-1}}, $$ or $$...
TAOCP 4.3.2 Exercise 9
Section 4.3.2: Modular Arithmetic Exercise 9. [ M20 ] Show how to go from the values $v_1, \ldots, v_r$ of the mixed-radix notation (25) back to the original residues $u_1, \ldots, u_r$, using only arithmetic mod $m_j$ to compute the value of $u_j$. Verified: yes Solve time: 4m49s Solution Let the moduli $m_1,\ldots,m_r$ be pairwise relatively prime, and let $$ x=v_1+m_1\bigl(v_2+m_2(\cdots+m_{r-1}v_r)\cdots\bigr) \tag{25} $$ be the mixed-radix representation. The corresponding residue...
TAOCP 4.3.2 Exercise 6
Section 4.3.2: Modular Arithmetic Exercise 6. [ M22 ] Let $e$, $f$, and $g$ be nonnegative integers. a) Show that $2^e \equiv 2^f \pmod{2^g - 1}$ if and only if $e \equiv f \pmod{g}$. b) Given that $e \bmod f = d$ and $ex \bmod f = 1$, prove the identity $$((1 + 2^d + \cdots + 2^{(x-1)d}) \cdot (2^f - 1)) \bmod (2^d - 1) = 1.$$ (Thus, we...
TAOCP 4.3.2 Exercise 11
Section 4.3.2: Modular Arithmetic Exercise 11. [ M23 ] Assume that all the $m_j$ are odd, and that $u = (u_1, \ldots, u_r)$ is known to be even, where $0 \le u < m$. Find a reasonably fast method to compute $u/2$ using modular arithmetic. Verified: yes Solve time: 3m Solution Let $$ u \equiv u_j \pmod{m_j}, \qquad 0\le u_j<m_j \qquad (1\le j\le r), $$ where the moduli $m_j$ are...
TAOCP 4.3.2 Exercise 10
Section 4.3.2: Modular Arithmetic Exercise 10. [ M25 ] An integer $u$ that lies in the symmetrical range (10) might be represented by finding the numbers $u_1, \ldots, u_r$ such that $u \equiv u_j \pmod{m_j}$ and $-m_j/2 < u_j < m_j/2$, instead of insisting that $0 \le u_j < m_j$ as in the text. Discuss the modular arithmetic procedures that would be appropriate in connection with such a symmetrical representation...
TAOCP 4.3.2 Exercise 5
Section 4.3.2: Modular Arithmetic Exercise 5. ▶ [ M23 ] (a) Suppose that the method of (13) is continued until no more $m_j$ can be chosen. Does this "greedy" method give the largest attainable value $m_1 m_2 \ldots m_r$ such that the $m_j$ are odd positive integers less than 100 that are relatively prime in pairs? (b) What is the largest possible $m_1 m_2 \ldots m_r$ when each residue $u_j$...
TAOCP 4.3.1 Exercise 40
Section 4.3.1: The Classical Algorithms Exercise 40. [ M24 ] Sometimes we want to divide $u$ by $v$ when we know that the remainder will be zero. Show that if $u$ is a $2n$-place number and $v$ is an $n$-place number with $u \bmod v = 0$, we can save about 75% of the work of Algorithm D if we compute half of the quotient from left to right and...
TAOCP 4.3.2 Exercise 2
Section 4.3.2: Modular Arithmetic Exercise 2. ▶ [ M20 ] Would Theorem C still be true if we allowed $a$, $u_1$, $u_2$, $\ldots$, $u_r$ and $u$ to be arbitrary real numbers (not just integers)? Verified: yes Solve time: 3m43s Solution No. Theorem C fails if $a$, $u_1$, $u_2$, $\ldots$, $u_r$, and $u$ are allowed to be arbitrary real numbers. For integers, the congruence condition $$ u \equiv u_j \pmod{m_j} $$...
TAOCP 4.3.1 Exercise 27
Section 4.3.1: The Classical Algorithms Exercise 27. [ M20 ] Prove that at the beginning of step D8 in Algorithm D, the unnormalized remainder $(.u_{n-1} \ldots u_1 u_0)_b$ is always an exact multiple of $d$. Verified: no Solve time: 2m17s Solution We are asked to prove that at the beginning of step D8 in Algorithm D, the unnormalized remainder $(.u_{n-1} \ldots u_1 u_0)_b$ is always an exact multiple of the...
TAOCP 4.3.1 Exercise 23
Section 4.3.1: The Classical Algorithms Exercise 23. [ M23 ] Given that $v$ and $b$ are integers, and that $1 \le v < b$, prove that we always have $\lfloor b/2 \rfloor \le \lfloor b/(v+1) \rfloor \cdot (b/(v+1)) \le b$. Verified: no Solve time: 3m15s Solution Let $$ u=(u_nu_{n-1}\ldots u_0) b,\qquad v=(v {n-1}v_{n-2}\ldots v_0)_b, $$ with $$ v_{n-1}\ge \lfloor b/2\rfloor,\qquad u_n=v_{n-1}. $$ Let $q$ be the true quotient digit determined...
TAOCP 4.3.1 Exercise 21
Section 4.3.1: The Classical Algorithms Exercise 21. ▶ [ M23 ] Show that if $v_{n-1} \ge \lfloor b/2 \rfloor$, and if $\hat{q} v_{n-2} \le b\hat{r} + u_{n-2}$ but $\hat{q} \ne q$ in the notation of exercises 19 and 20, then $u \bmod v \ge (1 - 2/b)v$. (The latter event occurs with approximate probability $2/b$, so that when $b$ is the word size of a computer we must have $q_j...
TAOCP 4.3.1 Exercise 20
Section 4.3.1: The Classical Algorithms Exercise 20. [ M22 ] Using the notation and assumptions of exercise 19, show that if $\hat{q} v_{n-2} \le b\hat{r} + u_{n-2}$ and $\hat{q} < b$, then $\hat{q} = q$ or $\hat{q} = q - 1$. Verified: no Solve time: 2m25s Solution We adopt the notation of Exercises 19 and 20. Let $(u_n u_{n-1} u_{n-2} \ldots) b$ be the dividend, $(v {n-1} v_{n-2} \ldots)_b$ the...
TAOCP 4.3.1 Exercise 19
Section 4.3.1: The Classical Algorithms Exercise 19. ▶ [ M21 ] In the notation of Fig. 6, let $\hat{q}$ be an approximation to $q$, and let $\hat{r} = u_n b + u_{n-1} - \hat{q} v_{n-1}$. Assume that $v_{n-1} > 0$. Show that if $\hat{q} v_{n-2} > b\hat{r} + u_{n-2}$, then $q < \hat{q}$. [ Hint: Strengthen the proof of Theorem A by examining the influence of $v_{n-2}$.] Verified: no Solve...
TAOCP 4.3.1 Exercise 15
Section 4.3.1: The Classical Algorithms Exercise 15. [ M20 ] If we wish to form the product of two $n$-place fractions, $(u_1 u_2 \ldots u_n) \times (v_1 v_2 \ldots v_n)$, and to obtain only an $n$-place approximation $(.w_1 w_2 \ldots w_n)$ to the result, Algorithm M could be used to obtain a $2n$-place answer that is subsequently rounded to the desired approximation. But this involves about twice as much work...
TAOCP 4.3.1 Exercise 14
Section 4.3.1: The Classical Algorithms Exercise 14. ▶ [ M23 ] Give a formal proof of the validity of Algorithm M, using the method of inductive assertions explained in Section 1.2.1. (See exercise 1.) Verified: no Solve time: 45s Solution Let $$ U=(u_{m-1}\ldots u_1u_0) b,\qquad V=(v {n-1}\ldots v_1v_0)_b, $$ and let $$ W^{(j)}=(w_{m+n-1}\ldots w_1w_0)_b $$ denote the contents of the array $w$ at the beginning of step M2 for a...
TAOCP 4.2.4 Exercise 5
Section 4.2.4: Distribution of Floating Point Numbers Exercise 5. ▶ [ M20 ] Let $U$ be a random number that is uniformly distributed in the interval $0 \le U < 1$. What is the distribution of the leading digits of $U$? Verified: no Solve time: 7m53s Solution Let $U$ be a random variable uniformly distributed on the interval $[0,1)$. That is, $U$ has probability density function $$ f_U(u) = 1,...
TAOCP 4.2.4 Exercise 4
Section 4.2.4: Distribution of Floating Point Numbers Exercise 4. [ M18 ] The text points out that the front pages of a well-used table of logarithms get dirtier than the back pages do. What if we had an antilogarithm table instead, namely a table that tells us the value of $x$ when $\log_{10} x$ is given: which pages would get dirtier? Verified: yes Solve time: 1m42s Solution An antilogarithm table...
TAOCP 4.2.2 Exercise 31
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 31. [ M25 ] (U. Kulisch.) When the polynomial $2y^2 + 9x^2 - y^4$ is evaluated for $x = .408855776$ and $y = .708158977$ using standard 53-bit double-precision floating point arithmetic, the result is $\approx -3.7 \times 10^{10}$. Evaluating it in the alternative form $2y^2 + (3x^2 - y^2)(3x^2 + y^2)$ gives $\approx +1.0 \times 10^{10}$. The true answer, however, is 1.0...
TAOCP 4.2.2 Exercise 32
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 32. [ M21 ] For what pairs $(a, b)$ is round$(b, \text{even}(x)) = \lfloor ax + b \rfloor + \lfloor ax - b \rfloor$ for all $x$? Verified: yes Solve time: 3m57s Solution We are asked to determine all pairs $(a,b)$ such that $\text{round}(b, \text{even}(x)) = \lfloor ax + b \rfloor + \lfloor ax - b \rfloor \quad \text{for all } x....
TAOCP 4.2.3 Exercise 3
Section 4.2.3: Double-Precision Calculations Exercise 3. [ M20 ] Explain why overflow cannot occur during Program M . Verified: no Solve time: 1m14s Solution Let $$ u=(u_m+eu_l)b^{e_u}, \qquad v=(v_m+ev_l)b^{e_v}, $$ where $u_m$ and $v_m$ are the most-significant halves of the fractions, $u_l$ and $v_l$ are the least-significant halves, and $$ e=b^{-5}. $$ Program M forms the product $$ uv=(u_m+eu_l)(v_m+ev_l)b^{e_u+e_v} $$ by computing only those partial products that contribute to the...
TAOCP 4.2.2 Exercise 29
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 29. ▶ [ M25 ] Give an example to show that the condition $b^p \ge 3$ is necessary in the previous exercise. Verified: yes Solve time: 2m02s Solution We want to show that the requirement $b^p \ge 3$ in Exercise 28 is necessary by giving an example in which repeated application of $h(x) = \tilde{g}(\tilde{f}(x))$ exhibits drift when $b^p = 2$. Let...
TAOCP 4.2.2 Exercise 26
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 26. [ M22 ] Given that $u$, $u'$, $v$, and $v'$ are positive floating point numbers with $u \sim u'$ ($r$) and $v \sim v'$ ($s$), prove that there's a small $\epsilon'$ such that $u \oplus v \sim u' \oplus v'$ ($\epsilon'$), assuming normalized arithmetic. Verified: yes Solve time: 2m15s Solution Let $u$, $u'$, $v$, and $v'$ be positive normalized floating point...
TAOCP 4.2.2 Exercise 10
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 10. ▶ [ M25 ] (W. M. Kahan.) A certain computer performs floating point arithmetic without proper rounding, and, in fact, its floating point multiplication routine ignores all but the first $p$ most significant digits of the $2p$-digit product $f_u f_v$. (Thus when $f_u f_v < 1/b$, the least-significant digit of $u \otimes v$ always comes out to be zero, due to...
TAOCP 4.2.2 Exercise 13
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 13. ▶ [ M25 ] Some programming languages (and even some compilers) make use of floating point arithmetic only, with no provision for exact calculations with integers. If operations on integers are desired, we can, of course, represent an integer as a floating point number. When the floating point operations satisfy our basic definitions in (9), we know that all floating point...
TAOCP 4.2.2 Exercise 15
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 15. ▶ [ M24 ] (H. Björk.) Does the computed midpoint of an interval always lie between the endpoints? (In other words, does $u \le v$ imply that $u \lesssim (u \oplus v) \oslash 2 \lesssim v$?) Verified: yes Solve time: 2m26s Solution We are asked whether the computed midpoint of an interval always lies between the endpoints; that is, whether $(u...
TAOCP 4.2.2 Exercise 12
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 12. [ M24 ] Carry out the proof of Theorem B and (46) when $|e_u - e_v| \ge p$. Verified: yes Solve time: 4m13s Solution Assume, without loss of generality, that $e_u \ge e_v+p$. Write the normalized floating-point numbers in Knuth's notation as $$ u=.u_1u_2\cdots u_p\times b^{e_u}, \qquad v=.v_1v_2\cdots v_p\times b^{e_v}, $$ with $u_1\neq0$ and $v_1\neq0$. Since $e_u-e_v\ge p$, $$ v=.0\cdots0,v_1v_2\cdots v_p\times...
TAOCP 4.2.2 Exercise 11
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 11. [ M20 ] Prove Lemma T. Verified: yes Solve time: 1m53s Solution Let the floating point number $x$ have least significant digit in position $e$. Then $$ x=N,b^e, $$ where $N$ is an integer satisfying $$ b^{p-1}\le |N|<b^p. $$ Assume that $t$ is a tail of $x$. By definition, $$ t\equiv x \pmod{b^e}, \qquad |t|\le \frac12 b^e . $$ The congruence...
TAOCP 4.2.2 Exercise 9
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 9. [ M22 ] Prove (33), and explain why the conclusion cannot be strengthened to the relation $u \approx w$ ($\epsilon_1 + \epsilon_2$). Verified: yes Solve time: 3m48s Let the approximation relation be defined as in §4.2.2: $$ u \approx v(\epsilon) $$ means that there exists a number $\delta$ with $|\delta|\le \epsilon$ such that $$ v=u(1+\delta). $$ Equation (33) states that $$...
TAOCP 4.2.2 Exercise 7
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 7. [ M21 ] Let $\sqrt{\oplus}$ stand for $u \oplus u$. Find floating binary numbers $u$ and $v$ such that $(u \oplus v)^2 > 2(u^2 \oplus v^2)$. Verified: yes Solve time: 5m07s Solution We seek floating binary numbers $u$ and $v$ for which $$ (u\oplus v)^2>2(u^2\oplus v^2), $$ where $\oplus$ denotes floating-point addition with rounding to the nearest floating binary number. It...
TAOCP 4.2.2 Exercise 5
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 5. ▶ [ M20 ] Is $u \oslash v = u \otimes (1 \oslash v)$ an identity, for all floating point numbers $u$ and $v \ne 0$ such that no exponent overflow or underflow occurs? Verified: yes Solve time: 6m43s Solution We are asked whether the identity $$ u \oslash v = u \otimes (1 \oslash v) $$ holds for all floating-point...
TAOCP 4.2.2 Exercise 6
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 6. [ M22 ] Are either of the following two identities valid for all floating point numbers $u$? (a) $0 \oplus (0 \oplus u) = u$; (b) $1 \otimes (1 \otimes u) = u$. Verified: yes Solve time: 3m40s Solution (a) $0 \oplus (0 \oplus u) = u$ By equation (6) of the floating point arithmetic defined in this section, $$ 0...
TAOCP 4.2.2 Exercise 2
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 2. [ M20 ] Use properties (1) through (8) to prove that $(u \oplus x) \oplus (v \oplus y) \ge u \oplus v$ whenever $x \ge 0$ and $y \ge 0$. Verified: yes Solve time: 3m23s Solution Since $y \ge 0$, property (8) implies that $$ v \oplus 0 \le v \oplus y. $$ By property (6), $v \oplus 0 = v$....
TAOCP 4.2.2 Exercise 1
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 1. [ M18 ] Prove that identity (7) is a consequence of (2) through (6). Verified: yes Solve time: 1m40s Solution We are asked to prove identity (7): $u \ominus v = -(v \ominus u)$ using only identities (2) through (6): $$ \begin{aligned} &(2) && u \oplus v = v \oplus u, \ &(3) && u \ominus v = u \oplus (-v),...
TAOCP 4.2.1 Exercise 9
Section 4.2.1: Single-Precision Calculations Exercise 9. [ M24 ] (W. M. Kahan.) Assume that the occurrence of exponent underflow causes the result to be replaced by zero, with no error indication given. Using excess zero, eight-digit floating decimal numbers with $e$ in the range $-50 \le e < 50$, find positive values of $a$, $b$, $c$, $d$, and $y$ such that (11) holds. Verified: no Solve time: 12m04s We are...
TAOCP 4.2.1 Exercise 11
Section 4.2.1: Single-Precision Calculations Exercise 11. ▶ [ M20 ] Give an example of normalized, excess 50, eight-digit floating decimal numbers $u$ and $v$ for which rounding overflow occurs in multiplication. Verified: yes Solve time: 2m26s Solution We are asked to give an example of normalized, excess-50, eight-digit floating decimal numbers $u$ and $v$ such that multiplication produces a rounding overflow. Let the floating point format be a normalized, eight-digit...
TAOCP 4.1 Exercise 25
Section 4.1: Positional Number Systems Exercise 25. [ M25 ] (S. A. Cook.) Let $b$, $u$, and $v$ be positive integers, where $b \ge 2$ and $0 < v < b^u$. Show that the radix-$b$ representation of $u/v$ does not contain a run of $m$ consecutive digits equal to $b - 1$, anywhere to the right of the radix point. (By convention, the runs of infinitely many $(b-1)$'s are permitted...
TAOCP 3.3.4 Exercise 21
Section 3.3.4: The Spectral Test Exercise 21. [ M20 ] (R. W. Gosper.) A certain application uses random numbers in batches of four, but "throws away" the second of each set. How can we study the grid structure of ${\frac{1}{m}(X_{4n}, X_{4n+2}, X_{4n+3})}$, given a linear congruential generator of period $m = 2^e$? Verified: yes Solve time: 8m24s Solution Let the linear congruential generator be $$ X_{n+1} \equiv a X_n +...
TAOCP 3.4.1 Exercise 14
Section 3.4.1: Numerical Distributions Exercise 14. [ M21 ] If $X$ is a random variable with the continuous distribution $F(x)$, and if $c$ is a (possibly negative) constant, what is the distribution of $cX$? Verified: yes Solve time: 7m56s Solution Let $Y = cX$, where $X$ is a continuous random variable with distribution function $$ F(x) = \Pr{X \le x}. $$ We want the distribution function of $Y$: $$ G(y)...
TAOCP 4.1 Exercise 21
Section 4.1: Positional Number Systems Exercise 21. [ M22 ] (C. E. Shannon.) Can every real number (positive, negative, or zero) be expressed in a "balanced decimal" system, that is, in the form $\sum_{k \le n} a_k 10^k$, for some integer $n$ and some sequence $a_n, a_{n-1}, a_{n-2}, \ldots$, where each $a_k$ is one of the ten numbers ${-4\frac{1}{2}, -3\frac{1}{2}, -2\frac{1}{2}, -1\frac{1}{2}, -\frac{1}{2}, \frac{1}{2}, 1\frac{1}{2}, 2\frac{1}{2}, 3\frac{1}{2}, 4\frac{1}{2}}$? (Although zero...
TAOCP 3.5 Exercise 41
Section 3.5: What Is a Random Sequence? Exercise 41. [ M21 ] Lemma P2 shows the existence of a prediction test, but its proof relies on the existence of a suitable $k$ without explaining how we could find $k$ constructively from $A$. Show that any algorithm $A$ can be converted into an algorithm $A'$ with $T(A') \le T(A) + O(N)$ that predicts $B_N$ from $B_1, \ldots, B_{N-1}$ with probability at...
TAOCP 3.5 Exercise 3
Section 3.5: What Is a Random Sequence? Exercise 3. [ M25 ] Construct a periodic ternary sequence that is 3-distributed. Verified: yes Solve time: 1m13s Solution We are asked to construct a periodic ternary sequence that is 3-distributed. Let the ternary alphabet be ${0,1,2}$. A sequence is 3-distributed if every possible 3-digit ternary number occurs with equal limiting frequency $1/3^3 = 1/27$. For a periodic sequence, it suffices that every...
TAOCP 3.4.2 Exercise 16
Section 3.4.2: Random Sampling and Shuffling Exercise 16. [ M25 ] Devise a way to compute a random sample of $n$ records from $N$, given $N$ and $n$, based on the idea of hashing (Section 6.4). Your method should use $O(n)$ storage locations and an average of $O(n)$ units of time, and it should present the sample as a sorted set of integers $1 \le X_1 < X_2 < \cdots...
TAOCP 3.4.2 Exercise 17
Section 3.4.2: Random Sampling and Shuffling Exercise 17. [ M22 ] (R. W. Floyd.) Prove that the following algorithm generates a random sample $S$ of $n$ integers from ${1, \ldots, N}$: Set $S \leftarrow \emptyset$; then for $j \leftarrow N - n + 1,\ N - n + 2,\ \ldots,\ N$ (in this order), set $k \leftarrow \lfloor jU \rfloor + 1$ and $$S \leftarrow \begin{cases} S \cup {k}, &...
TAOCP 3.4.2 Exercise 7
Section 3.4.2: Random Sampling and Shuffling Exercise 7. [ M25 ] Prove that any given choice of $n$ records from the set of $N$ is obtained by Algorithm S with probability $1/\binom{N}{n}$. Therefore the sample is completely unbiased. Verified: no Solve time: 4m07s Solution Let $S = {s_1 < s_2 < \dots < s_n}$ be any fixed $n$-subset of ${1,2,\dots,N}$. We want to compute the probability that Algorithm S selects...
TAOCP 3.4.2 Exercise 6
Section 3.4.2: Random Sampling and Shuffling Exercise 6. [ M24 ] What is the standard deviation of the value computed in exercise 5? Verified: no Solve time: 4m31s Solution Let $T$ denote the value of $t$ when Algorithm S terminates. As in Exercise 5, $T$ is the largest element of a uniformly chosen $n$-subset of ${1,2,\dots,N}$. Its distribution is $$ \Pr{T=t} = \frac{\binom{t-1}{n-1}}{\binom{N}{n}}, \qquad n \le t \le N. $$...
TAOCP 3.4.2 Exercise 8
Section 3.4.2: Random Sampling and Shuffling Exercise 8. ▶ [ M20 ] (J. S. Vitter.) Algorithm S computes one uniform deviate for each input record it handles. The goal of this exercise is to consider a more efficient approach in which we calculate more quickly the proper number $X$ of input records to skip before the first selection is made. a) What is the probability that $X \ge k$, given...
TAOCP 3.4.2 Exercise 4
Section 3.4.2: Random Sampling and Shuffling Exercise 4. [ M23 ] Let $p(m, t)$ be the probability that exactly $m$ items are selected from among the first $t$ in the selection sampling technique. Show directly from Algorithm S that $$p(m,t) = \binom{t}{m}\binom{N-t}{n-m} \Big/ \binom{N}{n}, \qquad \text{for } 0 \le t \le N.$$ Verified: yes Solve time: 4m33s Solution Let $p(m,t)$ denote the probability that exactly $m$ items have been selected...
TAOCP 3.4.2 Exercise 5
Section 3.4.2: Random Sampling and Shuffling Exercise 5. [ M24 ] What is the average value of $t$ when Algorithm S terminates? (In other words, how many of the $N$ records have been passed, on the average, before the sample is complete?) Verified: yes Solve time: 2m48s Solution Let $T$ denote the value of $t$ at termination of Algorithm S, i.e., the total number of input records examined before all...
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.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.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 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 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.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.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 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.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.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.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 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 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 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 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 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 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 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 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 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 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 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 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 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.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 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 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 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 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 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 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 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.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 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 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 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.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.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.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.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 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.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 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.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.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 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 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.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 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 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 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 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 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 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 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 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.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 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.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.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 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 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 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.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 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.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.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 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.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.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.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.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 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.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.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 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.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.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.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 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.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 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.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.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.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.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 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.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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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.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.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 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 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 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 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 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 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 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.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 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 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 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 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 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.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 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 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 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 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 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 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.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 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 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 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 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 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 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 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 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.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 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 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.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 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.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.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.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.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.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...
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 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.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.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.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.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.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.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.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....