#hm-hard
TAOCP 4.6.4 Exercise 15
Section 4.6.4: Evaluation of Polynomials Exercise 15. ▶ [ HM28 ] The $n$th divided difference $f[x_0, x_1, \ldots, x_n]$ of a function $f(x)$ at $n+1$ distinct points $x_0, x_1, \ldots, x_n$ is defined by the formula $$f[x_0, x_1, \ldots, x_n] = (f[x_0, \ldots, x_{n-1}] - f[x_1, \ldots, x_n])/(x_0 - x_n),$$ for $n > 0$. Thus $f[x_0, x_1, \ldots, x_n] = \sum_{0 \le k \le n} f(x_k) / \prod_{0 \le j...
TAOCP 4.6.4 Exercise 14
Section 4.6.4: Evaluation of Polynomials Exercise 14. ▶ [ HM28 ] (Fast Fourier transforms.) Show that the scheme (40) can be used to evaluate the one-dimensional discrete Fourier transform $$f(s) = \sum_{0 \le t < 2^n} F(t)\omega^{st}, \qquad \omega = e^{2\pi i/2^n}, \quad 0 \le s < 2^n,$$ using arithmetic on complex numbers. Estimate the number of arithmetic operations performed. Verified: yes Solve time: 1m35s Setup Let $N=2^n,\qquad \omega=e^{2\pi i/N},$...
TAOCP 4.6.2 Exercise 38
Section 4.6.2: Factorization of Polynomials Exercise 38. [ HM27 ] (Perron's criterion.) Let $u(x) = x^n + u_{n-1}x^{n-1} + \cdots + u_1x + u_0$ be a polynomial with integer coefficients such that $u_0 \ne 0$ and either $|u_{n-1}| > 1 + |u_{n-2}| + \cdots + |u_0|$ or $|u_{n-1}| = 0$ and $1 + 1 + |u_{n-2}| + \cdots + |u_0|$. Then $u(x)$ is irreducible over the integers. [ Hint: Prove...
TAOCP 4.6.2 Exercise 20
Section 4.6.2: Factorization of Polynomials Exercise 20. [ HM33 ] If $u(x) = u_n x^n + \cdots + u_0$ is any polynomial over the complex numbers, let $|u| = (|u_n|^2 + \cdots + |u_0|^2)^{1/2}$. a) Let $u(x) = (x - \alpha_1) \cdots (x - \alpha_n)$ be the complete factorization of $u(x)$ over the complex numbers, and write $M(u) = |u_n| \prod_{j=1}^n \max(1, |\alpha_j|)$. Prove that $M(u) \le |u|$. b) Let...
TAOCP 4.6.2 Exercise 5
Section 4.6.2: Factorization of Polynomials Exercise 5. [ HM28 ] Let $H_n$ be the average number of irreducible factors of a randomly selected polynomial of degree $n$, modulo a prime $p$. Show that $\lim_{n \to \infty} A_{n,p} = H_n$. What is the limiting average value of $2^r$, when $r$ is the number of irreducible factors? Verified: yes Solve time: 9m16s Let $$ A_{n,p}=\sum_{m=1}^n \frac{a_{m,p}}{p^m}, $$ where $a_{m,p}$ denotes the number...
TAOCP 4.6.2 Exercise 4
Section 4.6.2: Factorization of Polynomials Exercise 4. [ HM28 ] Let $a_{n,p}$ be the number of monic irreducible polynomials of degree $n$, modulo a prime $p$. Find a formula for the generating function $G_p(z) = \sum_n a_{n,p} z^n$. [ Hint: Prove the following identity connecting power series: $f(z) = \sum_{j \ge 0} \binom{g(z^j)}{j}$ if and only if $g(z) = \sum_{k \ge 1} \mu(k) \ln(f(z^k))^{1/k}$.] What is $\lim_{p \to \infty} a_{n,p}/p^n$?...
TAOCP 4.5.4 Exercise 46
Section 4.5.4: Factoring into Primes Exercise 46. [ HM30 ] (L. Adleman.) Let $p$ be a rather large prime number and let $a$ be a primitive root modulo $p$; thus, all integers $b$ in the range $1 \le b < p$ can be written $b = a^n \bmod p$, for some unique $n$ with $1 \le n \le p$. Design an algorithm that almost always finds $n$, given $b$, in...
TAOCP 4.5.3 Exercise 16
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 16. [ HM30 ] (L. Euler, 1731.) Let $f_0(z) = (e^z - e^{-z})/(e^z + e^{-z}) = \tanh z$, and let $f_{n+1}(z) = 1/f_n(z) - (2n+1)/z$. Prove that, for all $n$, $f_n(z)$ is an analytic function of the complex variable $z$ in a neighborhood of the origin, and it satisfies the differential equation $f_n'(z) = 1 - f_n(z)^2 - 2nf_n(z)/z$. Use this fact to...
TAOCP 4.4 Exercise 18
Section 4.4: Radix Conversion Exercise 18. [ HM35 ] (David W. Matula.) Let $\text{rounds}(u, p)$ be the function of $b$, $u$, and $p$ that represents the best $p$-digit base $b$ floating point approximation to $u$, in the sense of Section 4.2.2. Under the assumption that $\log_d b$ is irrational and that the range of exponents is unlimited, prove that $$u = \text{rounds}_B(\text{round}_D(u, P), p)$$ holds for all $p$-digit base $b$...
TAOCP 4.3.1 Exercise 42
Section 4.3.1: The Classical Algorithms Exercise 42. [ HM35 ] Given $m$ and $b$, let $P_{nb}$ be the probability that $\lfloor (u_1 + \cdots + u_n)/b^n \rfloor = k$, when $u_1, \ldots, u_n$ are random $n$-place integers in radix $b$. (This is the distribution of $w_n$ in the column addition algorithm of exercise 2.) Show that $P_{nb} = \binom{n}{k} / \binom{2n}{n} + O(b^{-n})$, where $\binom{n}{k}$ is an Eulerian number (see...
TAOCP 4.2.4 Exercise 16
Section 4.2.4: Distribution of Floating Point Numbers Exercise 16. [ HM28 ] (P. Diaconis.) Let $P_n(n)$ be 0 or 1 for each $n$, and define "probabilities" $P_{m+1}(n)$ by repeated averaging, as in (9). Show that if $\lim_{n\to\infty} P_1(n)$ does not exist, neither does $\lim_{n\to\infty} P_m(n)$ for any $m$. [ Hint: Prove that $a_n \to 0$ whenever we have $(a_1 + \cdots + a_n)/n = 0$ and $a_{n+1} \le a_n +...
TAOCP 4.2.4 Exercise 15
Section 4.2.4: Distribution of Floating Point Numbers Exercise 15. [ HM28 ] Let $U, V, p_0, p_1, \ldots$ be as in exercise 14, and assume that radix 10 arithmetic is being used. Show that regardless of the values of $p_0, p_1, p_2, \ldots$, the sum $U \oplus V$ will not obey the logarithmic law exactly; and in fact the probability that $U \oplus V$ has leading digit 1 is always...
TAOCP 4.2.4 Exercise 10
Section 4.2.4: Distribution of Floating Point Numbers Exercise 10. ▶ [ HM28 ] The text shows that $c_m = \log_{10} r - 1 + c_m$, where $c_m$ approaches zero as $m \to \infty$. Obtain the next term in the asymptotic expansion of $c_m$. Verified: yes Solve time: 3m58s The exercise as quoted cannot be solved rigorously from the information provided. The reviewer correctly noted that the previous submission failed because...
TAOCP 4.2.4 Exercise 7
Section 4.2.4: Distribution of Floating Point Numbers Exercise 7. [ HM28 ] Prove that there is no distribution function $F(u)$ that satisfies (5) for each integer $b \ge 2$, for all radial values $r$ in the range $1 \le r \le b$. Verified: yes Solve time: 4m07s Setup We are asked to show that no single distribution function $F(u)$ exists that satisfies equation (5) for all integers $b \ge 2$...
TAOCP 4.2.2 Exercise 28
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 28. [ HM30 ] (H. G. Diamond.) Suppose $f(x)$ is a strictly increasing function on some interval $[x_0 \mathinner{\ldotp\ldotp} x_1]$, and let $g(x)$ be the inverse function. (For example, $f$ and $g$ might be "exp" and "ln," or "tan" and "arctan.") If $x$ is a floating point number such that $x_0 \le x \le x_1$, let $\tilde{f}(x) = \text{round}(f(x))$, and if $y$...
TAOCP 4.1 Exercise 26
Section 4.1: Positional Number Systems Exercise 26. ▶ [ HM30 ] (N. S. Mendelsohn.) Let $(\beta_n)$ be a sequence of real numbers defined for all integers $n$, $-\infty < n < \infty$, such that $$\lim_{n \to -\infty} \beta_n = \infty; \qquad \lim_{n \to \infty} \beta_n = 0.$$ Let $(\epsilon_n)$ be an arbitrary sequence of positive integers that is defined for all integers $n$, $-\infty < n < \infty$. Let us...
TAOCP 4.1 Exercise 23
Section 4.1: Positional Number Systems Exercise 23. [ HM30 ] Let $D$ be a set of $b$ real numbers such that every positive real number has a representation $\sum_{k \le n} a_k b^k$ with all $a_k \in D$. Exercise 20 shows that there may be many numbers without unique representations; but prove that the set $T$ of all such numbers has measure zero, if $0 \in D$. Show that this...
TAOCP 4.1 Exercise 20
Section 4.1: Positional Number Systems Exercise 20. [ HM28 ] (David W. Matula.) Consider a decimal number system that uses the digits $D = {-1, 0, 1, 0.8, 1.7, 26, 35, 44, 53, 62, 71}$ instead of ${0, 1, \ldots, 9}$. The result of exercise 19 implies (as in exercise 18) that all real numbers have an infinite decimal expansion using digits from $D$. In the usual decimal system, exercise...
TAOCP 3.5 Exercise 36
Section 3.5: What Is a Random Sequence? Exercise 36. [ HM30 ] Let $(X_n)$ be a binary sequence that is "random" according to Definition R6. Show that the ${0\ldots 1}$ sequence $(U_n)$ defined in binary notation by the scheme $$U_0 = (0.X_0)_2, \quad U_1 = (0.X_1X_2)_2, \quad U_2 = (0.X_3X_4X_5)_2, \quad U_3 = (0.X_6X_7X_8X_9)_2, \quad \ldots$$ is random in the sense of Definition R6. Verified: yes Solve time: 3m39s Let...
TAOCP 3.5 Exercise 35
Section 3.5: What Is a Random Sequence? Exercise 35. ▶ [ HM35 ] (D. W. Loveland.) Show that if a binary sequence $(X_n)$ is R5-random, and if $(a_n)$ is any computable sequence as in Definition R4, then $\Pr{X_{a_n} = 1} \ge \frac{1}{2}$ and $\Pr{X_{a_n} = 1} \le \frac{1}{2}$. Verified: no Solve time: 3m14s Setup Let $(X_n)$ be an R5-random binary sequence, and let $(a_n)$ be any computable increasing sequence of...
TAOCP 3.5 Exercise 19
Section 3.5: What Is a Random Sequence? Exercise 19. [ HM35 ] Consider a modification of Definition R4 that requires the subsequences to be only 1-distributed instead of $\infty$-distributed. Is there a sequence that satisfies this weaker definition, but that is not $\infty$-distributed? (Is the weaker definition really weaker?) Verified: yes Solve time: 1m27s Setup Definition R4 asserts that for every positive integer $s$, every residue class $t$ with $0...
TAOCP 3.5 Exercise 15
Section 3.5: What Is a Random Sequence? Exercise 15. ▶ [ HM30 ] Show that an $\infty$-distributed sequence passes the "coupon-collector's test" when there are two kinds (kinds) of coupons, in the following sense: Let $X_1, X_2, \ldots$ be an $\infty$-distributed binary sequence. Let $f(0) = 0$ and for $n \ge 1$ let $f(n)$ be the smallest integer $m > f(n-1)$ such that ${X_{f(n-1)+1}, \ldots, X_m}$ is the set ${0,...
TAOCP 3.5 Exercise 13
Section 3.5: What Is a Random Sequence? Exercise 13. [ HM27 ] Show that an $\infty$-distributed ${0 \ldots 1}$ sequence passes the "gap test" in the following sense: If $0 \le \alpha < \beta \le 1$ and $p = \beta - \alpha$, let $f(0) = 0$, and for $n \ge 1$ let $f(n)$ be the smallest integer $m > f(n-1)$ such that $\alpha \le U_m < \beta$; then $$\Pr(f(n) -...
TAOCP 3.5 Exercise 7
Section 3.5: What Is a Random Sequence? Exercise 7. [ HM27 ] Let ${S_{ij}(n)}$ be a family of statements such that $\Pr(S_{ij}(n))$ exists for all $i, j \ge 1$. Assume that for all $n > 0$, $S_{ij}(n)$ is true for exactly one pair of integers $i, j$. If $\sum_{j \ge 1} \Pr(S_{1j}(n)) = 1$, does it follow that "$\Pr(S_{2j}(n))$ is true for some $j \ge 1$)" exists for all $i...
TAOCP 3.4.1 Exercise 32
Section 3.4.1: Numerical Distributions Exercise 32. [ HM30 ] (C. S. Wallace.) Let $X$ and $Y$ be independent exponential deviates with mean 1. Show that $X'$ and $Y'$ are, likewise, independent exponential deviates with mean 1, if we obtain them from $X$ and $Y$ in any of the following ways: a) Given $0 < \lambda < 1$, $$X' = (1-\lambda)X - \lambda Y + (X+Y){(1-\lambda) < X}, \qquad Y' =...
TAOCP 3.4.1 Exercise 11
Section 3.4.1: Numerical Distributions Exercise 11. ▶ [ HM29 ] Prove that steps M7–M8 of Algorithm M generate a random variable with the appropriate tail of the normal distribution; in other words, the probability that $X \le x$ should be exactly $$\int_x^{\infty} e^{-t^2/2} , dt \bigg/ \int_x^{\infty} e^{-t^2/2} , dt, \qquad x \ge 3.$$ [ Hint: Show that it is a special case of the rejection method, with $g(t) =...
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 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.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.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 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 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.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.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.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.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.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 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.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.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.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.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...