#hm-hard
TAOCP 3.4.1 Exercise 28
Section 3.4.1: Numerical Distributions Exercise 28. [ HM35 ] (R. P. Brent.) Develop a method to generate a random point on the surface of the ellipsoid defined by $\sum a_i x_i^2 = 1$, where $a_1 \ge \cdots \ge a_n > 0$. Verified: yes Solve time: 1m43s Setup Let $$ \qquad a_1\ge \cdots \ge a_n>0. $$ The problem is to generate a random point on the surface of the ellipsoid $E$,...
TAOCP 3.4.1 Exercise 21
Section 3.4.1: Numerical Distributions Exercise 21. [ HM29 ] Derive formulas for the quantities $A$, $R$, $I$, and $E$ defined in exercise 20. (For $I$ and especially $E$ you may wish to use an interactive computer algebra system.) Show that $e^{1/e} \approx 1.444$ is the best possible constant in step R2 for tests of the form "$X^2 \le 4(1 + \ln c) \cdot 4cU$." Verified: no Solve time: 4m46s Let...
TAOCP 3.3.4 Exercise 9
Section 3.3.4: The Spectral Test Exercise 9. [ HM32 ] (C. Hermite, 1846.) Let $f(x_1, \ldots, x_t)$ be a positive definite quadratic form, defined by the matrix $U$ as in (17), and let $\theta$ be the minimum value of $f$ at nonzero integer points. Prove that $\theta \le \left(\frac{4}{3}\right)^{(t-1)/2} |\det U|^{2/t}$. [ Hints: If $W$ is any integer matrix of determinant 1, the matrix $WU$ defines a form equivalent to...
TAOCP 3.2.2 Exercise 37
Section 3.2.2: Other Methods Exercise 37. ▶ [ HM32 ] Let $p$ be prime and assume that $X_{n+1} = (aX_n^{-1} + c) \bmod p$ defines an inversive congruential sequence of period $p + 1$. Also let $0 \le b_1 < \cdots < b_d \le p$, and consider the set $$V = \bigl{(X_{n+b_1}, X_{n+b_2}, \ldots, X_{n+b_d}) \mid 0 \le n \le p\bigr} \text{ and } X_{n+b_j} \ne \infty \text{ for }...
TAOCP 3.2.2 Exercise 35
Section 3.2.2: Other Methods Exercise 35. [ HM35 ] How many pairs $(a, c)$ satisfy the conditions of exercise 34? Verified: yes Solve time: 2m48s Exercise 3.2.2.35 [ HM35 ] Problem: Determine the number of pairs $(a,c)\in \mathbb{F}_p \times \mathbb{F}_p$ satisfying the conditions of Exercise 34, i.e., such that the inversive congruential sequence $$ x_{n+1} \equiv a x_n^{-1} + c \pmod p, \quad x_n \neq 0 $$ has maximal period...
TAOCP 2.2.1 Exercise 12
Section 2.2.1: Stacks, Queues, and Deques Exercise 12. [ HM34 ] Compute the asymptotic values of the quantities $a_n$ and $b_n$ in exercises 4 and 11. Verified: no Solve time: - Setup Let $a_n$ denote the number of permutations obtainable with a stack, as defined in Exercise 4, and let $b_n$ denote the number of permutations obtainable with an input-restricted deque, equivalently with an output-restricted deque by Exercise 9. Exercise...
TAOCP 1.3.3 Exercise 22
Section 1.3.3: Applications to Permutations Exercise 22. [ HM34 ] (The following approach, due to L. Shepp and S. P. Lloyd, gives a convenient and powerful method for solving problems related to the cycle structure of random permutations.) Instead of regarding the number, $n$, of objects as fixed, and the permutation variable, let us assume instead that we independently choose the quantities $\alpha_1, \alpha_2, \alpha_3, \ldots$ appearing in exercises 20...
TAOCP 1.2.9 Exercise 21
Section 1.2.9: Generating Functions Exercise 21. [ HM30 ] Set up the generating function for the sequence $\langle n! \rangle$ and study properties of this function. Verified: yes Solve time: 1m06s Setup Let $\langle a_n \rangle = \langle n! \rangle$. Define its ordinary generating function by $$ G(z) = \sum_{n \ge 0} n! , z^n. \tag{1} $$ The task is to construct $G(z)$ and analyze its properties using the operations...
TAOCP 1.2.9 Exercise 19
Section 1.2.9: Generating Functions Exercise 19. [ HM32 ] (C. F. Gauss, 1812.) The sums of the following infinite series are well known: $$ 1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots = \ln 2; \qquad 1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots = \frac{\pi}{4}; $$ $$ 1-\frac{1}{4}+\frac{1}{7}-\frac{1}{10}+\cdots = \frac{\pi\sqrt{3}}{9} + \frac{1}{3}\ln 2. $$ Using the definition $$ H_x = \sum_{n \ge 1}\left(\frac{1}{n}-\frac{1}{n+x}\right) $$ found in the answer to exercise 1.2.7-24, these series may be written respectively as $$ 1 - \frac{1}{2}H_{1/2}; \qquad...
TAOCP 1.2.6 Exercise 66
Section 1.2.6: Binomial Coefficients Exercise 66. [ HM30 ] Suppose $x,y,z$ are real numbers satisfying $$ \binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}, $$ where $x \ge n-1$, $y \ge n-1$, $z > n-2$, and $n$ is an integer $\ge 2$. Prove that $$ \binom{x}{n-1} \le \binom{y}{n-1} + \binom{z}{n-2} \quad \text{if and only if } y \ge z, $$ and $$ \binom{x}{n+1} \le \binom{y}{n+1} + \binom{z}{n} \quad \text{if and only if }...
TAOCP 1.2.6 Exercise 65
Section 1.2.6: Binomial Coefficients Exercise 65. [ HM35 ] Prove Eqs. (59) and (60). Verified: no Solve time: - I need the statements of Eqs. (59) and (60) from Section 1.2.6 to write a rigorous proof in the requested format. The excerpt you provided ends at Eq. (13), and Eqs. (59)–(60) occur later in the section. Please paste the text containing Eqs. (59) and (60), or upload the relevant page(s),...
TAOCP 1.2.6 Exercise 38
Section 1.2.6: Binomial Coefficients Exercise 38. [ HM30 ] (C. Ramus, 1834.) Generalizing the result of the preceding exercise, show that we have the formula $$ \binom{n}{k} + \binom{n}{m+k} + \binom{n}{2m+k} + \cdots = \frac{1}{m}\sum_{0 \le j < m}\left(2\cos\frac{j\pi}{m}\right)^n \cos\frac{j(n-2k)\pi}{m}. $$ Verified: no Solve time: - Setup Let $n$ and $m$ be integers with $m \ge 1$, and let $k$ be an integer. We are asked to prove the identity...
TAOCP 1.2.6 Exercise 25
Section 1.2.6: Binomial Coefficients Exercise 25. [ HM30 ] Let the polynomial $A_n(x,t)$ be defined as in Example 4. Let $z=x^{t+1}-x^t$. Prove that $\sum_k A_k(r,t)z^k = x^r$, provided that $x$ is close enough to 1. Verified: no Solve time: - Setup Let $A_n(x,t)$ be the polynomial defined in Example 4 of Section 1.2.6. We are given $$ z = x^{t+1} - x^t $$ and are asked to prove that $$...
TAOCP 1.2.4 Exercise 39
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 39. [ HM35 ] A function $f$ for which $$f(x)+f\left(x+\frac1n\right)+\cdots+f\left(x+\frac{n-1}{n}\right)=f(nx),$$ whenever $n$ is a positive integer, is called a replicative function. The previous exercise establishes the fact that $\lfloor x \rfloor$ is replicative. Show that the following functions are replicative: a) $f(x)=x-\tfrac12$; b) $f(x)=[x \text{ is an integer}]$; c) $f(x)=[x \text{ is a positive integer}]$; d) $f(x)=[\text{there exists a rational number...
TAOCP 1.2.11.3 Exercise 17
Section 1.2.11.3: Some Asymptotic Calculations Exercise 17. [ HM29 ] (K. W. Miller.) Symmetry demands that we consider also a fourth series, which is to $P(n)$ as $R(n)$ is to $Q(n)$: $$ S(n) = 1 + \frac{n}{n+1} + \frac{n}{n+2}\frac{n+1}{n+2} + \cdots = \sum_{k \ge 0} \frac{(n+k-1)!}{(n-1)!(n+k)^k}. $$ What is the asymptotic behavior of this function? Verified: yes Solve time: 1m56s Setup Define $$ S(n)=\sum_{k\ge0}\frac{(n+k-1)!}{(n-1)!(n+k)^k}. $$ The problem asks for an...
TAOCP 1.2.11.3 Exercise 19
Section 1.2.11.3: Some Asymptotic Calculations Exercise 19. [ HM30 ] (Watson's lemma.) Show that if the integral $$ C_n = \int_0^\infty e^{-nx} f(x),dx $$ exists for all large $n$, and if $f(x)=O(x^\alpha)$ for $0 \le x \le r$, where $r>0$ and $\alpha>-1$, then $$ C_n = O(n^{-1-\alpha}). $$ Verified: yes Solve time: 6m56s The reviewer is correct: the original proof fails because it implicitly assumes absolute convergence of a Laplace...
TAOCP 1.2.11.3 Exercise 20
Section 1.2.11.3: Some Asymptotic Calculations Exercise 20. [ HM30 ] Let $$ u = w + \frac{1}{3}w^2 + \frac{1}{36}w^3 - \frac{1}{270}w^4 + \cdots = \sum_{k=1}^{\infty} c_k w^k $$ be the power series solution to the equation $$ w = \left(u^2 - \frac{2}{3}u^3 + \frac{2}{4}u^4 - \frac{2}{5}u^5 + \cdots\right)^{1/2}, $$ as in (12). Show that $$ Q(n) + 1 = \sum_{k=1}^{m-1} k c_k \Gamma(k/2)\left(\frac{n}{2}\right)^{1-k/2} O(n^{1-m/2}) $$ for all $m \ge 1$....
TAOCP 1.2.11.3 Exercise 7
Section 1.2.11.3: Some Asymptotic Calculations Exercise 7. [ HM30 ] In the evaluation of $I_2$, we had to consider $$ \int_0^y e^{-u}\left(1+\frac{u}{x}\right)^x du. $$ Give an asymptotic representation of $$ \int_0^{yx^{1/4}} e^{-u}\left(1+\frac{u}{x}\right)^x du $$ to terms of order $O(x^{-2})$, when $y$ is fixed and $x$ is large. Verified: no Solve time: 6m22s Let $$ J(x)=\int_0^{y x^{1/4}} e^{-u}\left(1+\frac ux\right)^x,du, $$ where $y$ is fixed and $x\to\infty$. We seek an asymptotic expansion...
TAOCP 1.2.10 Exercise 6
Section 1.2.10: Analysis of an Algorithm Exercise 6. [ HM27 ] We've computed the mean and the variance of the important probability distributions (8), (18), (20). What is the third semi-invariant, $\kappa_3$, in each of those cases? Verified: yes Solve time: 2m03s Setup For a probability generating function $$ G(z)=\sum_{k\ge0}p_k z^k, $$ the third semi-invariant (third cumulant) is $$ \kappa_3 = \left.\frac{d^3}{dt^3}\log G(e^t)\right|_{t=0}. $$ Since $$ K(t)=\log G(e^t), $$ we...
TAOCP 1.2.11.2 Exercise 5
Section 1.2.11.2: Euler's Summation Formula Exercise 5. [ HM30 ] Given that $$ n! = \kappa \sqrt{n}\left(\frac{n}{e}\right)^n\left(1+O!\left(\frac{1}{n}\right)\right), $$ show that $\kappa=\sqrt{2\pi}$ by using Wallis's product. Verified: yes Solve time: 59s Setup Assume $$ n! = \kappa \sqrt{n}\left(\frac{n}{e}\right)^n\left(1+O!\left(\frac{1}{n}\right)\right) \tag{1} $$ for a constant $\kappa>0$. Define the central binomial coefficient $$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2}. \tag{2} $$ Substituting (1) into (2) gives an asymptotic expression for $\binom{2n}{n}$ in terms of $\kappa$. Wallis’s product...
TAOCP 1.2.11.2 Exercise 7
Section 1.2.11.2: Euler's Summation Formula Exercise 7. [ HM32 ] What is the approximate value of $1^1 2^2 3^3 \cdots n^n$? Verified: yes Solve time: 44s Setup Let $$ P_n = 1^1 2^2 3^3 \cdots n^n = \prod_{k=1}^n k^k. $$ We are asked to find an approximate value of $P_n$ for large $n$. Following the argument in Section 1.2.11.2, we will take logarithms to convert the product into a sum,...
TAOCP 1.2.11.3 Exercise 8
Section 1.2.11.3: Some Asymptotic Calculations Exercise 8. [ HM30 ] If $f(x)=O(x^r)$ as $x\to\infty$ and $0 \le r < 1$, show that $$ \int_0^{f(x)} e^{-u}\left(1+\frac{u}{x}\right)^x du = \int_0^{f(x)} \exp\left( -\frac{u^2}{2x} \frac{u^3}{3x^2} \cdots \frac{(-1)^{m-1}u^m}{mx^{m-1}} \right),du O(x^{-s}), $$ if $m=\lceil (s+2r)/(1-r)\rceil$. d) Show that the asymptotic expansion of $$ \sum_{k \ge 0} k^t e^{-k^2/2n} $$ for fixed $t \ge 0$ can be obtained by Euler's summation formula. e) Finally therefore $$ \sum_{k=0}^{n}...
TAOCP 1.2.11.2 Exercise 6
Section 1.2.11.2: Euler's Summation Formula Exercise 6. [ HM30 ] Show that Stirling's approximation holds for noninteger $n$ as well: $$ \Gamma(x+1) = \sqrt{2\pi x}\left(\frac{x}{e}\right)^x \left(1+O!\left(\frac{1}{x}\right)\right), \qquad x \ge a > 0. $$ Verified: yes Solve time: 4m03s Let $$ S(x)=\sqrt{2\pi x}\left(\frac{x}{e}\right)^x . $$ We must prove that for every fixed $a>0$, $$ \Gamma(x+1)=S(x)\left(1+O!\left(\frac1x\right)\right), \qquad x\ge a. $$ The corresponding formula for integers is already known from Exercise 5: $$...
TAOCP 1.2.10 Exercise 14
Section 1.2.10: Analysis of an Algorithm Exercise 14. [ HM30 ] (A. de Moivre.) Using the conventions of the previous exercise, show that the binomial distribution $G_n(z)$ given by Eq. (18) approaches the normal distribution. Verified: yes Solve time: 47s Setup Let $$ G_n(z)=(q+pz)^n,\qquad q=1-p. $$ From the preceding analysis of the binomial process, the mean and variance are $$ \mu_n = pn,\qquad \sigma_n^2 = pqn. $$ The expression to...
TAOCP 1.2.1 Exercise 15
Section 1.2.1: Mathematical Induction Exercise 15. ▶ [ HM28 ] ( Generalized induction .) The text shows how to prove statements $P(n)$ that depend on a single integer $n$, but it does not describe how to prove statements $P(m, n)$ depending on two integers. In these circumstances a proof is often given by some sort of “double induction,” which frequently seems confusing. Actually, there is an important principle more general...