#hm-simple
TAOCP 5.2.1 Exercise 15
Section 5.2.1: Sorting by Insertion Exercise 15. ▶ [ HM3 ] Let $g_0(z)$, $g_n(z)$, $h_n(z)$, and $\tilde{h}_n(z)$ be $\sum z^{\text{total weight of path}}$ summed over all lattice paths of length $2n$ from $(0,0)$ to $(n,n)$, where the weight is defined as in Fig. 11, subject to certain restrictions on the vertices on the paths: For $h_n(z)$, there is no restriction, but for $g_n(z)$ the path must avoid all vertices $(i,j)$...
TAOCP 5.2.1 Exercise 18
Section 5.2.1: Sorting by Insertion Exercise 18. [ HM2 ] For large $N$ the sum (6) can be estimated as $$\frac{1}{4} \frac{N^2}{h_{t-1}} - \frac{\sqrt{\pi}}{8} \left( \frac{N^{3/2} h_{t-1}^{1/2}}{h_{t-2}} + \cdots + \frac{N^{3/2} h_1^{1/2}}{h_0} \right).$$ What real values of $h_{t-1}, \ldots, h_0$ minimize this expression when $N$ and $t$ are fixed and $h_0 = 1$? Verified: no Solve time: 7m44s We minimize the asymptotic estimate for the sum (6): [ E =...
TAOCP 7.2.2.1 Exercise 358
Section 7.2.2.1: Dancing Links Exercise 358. [ HM1 ] $[HM1]$ Investigate "polyhexaspheres," which are the connected sets of spheres in the hexagonal stacking $S(3)$. (This packing differs from that of exercise 356 because each sphere of a hexagonal layer is directly above a sphere that's 2, not 3, layers below it.) Verified: no Solve time: 34s Represent the centers of the spheres by coordinates in the hexagonal stacking, using two-dimensional...
TAOCP 7.2.1.6 Exercise 106
Section 7.2.1.6: Generating All Trees Exercise 106. ▶ [ HM7 ] Find the total number of spanning trees in (a) an $m \times n$ grid $P_m \mathbin{\square} P_n$; (b) an $m \times n$ cylinder $P_m \mathbin{\square} C_n$; (c) an $m \times n$ torus $C_m \mathbin{\square} C_n$. Do these numbers tend to have many small prime factors? Hint: Show that the numbers for $P_n$ and $C_n$ can be expressed as $4\sin^2\frac{j\pi}{2n}$...
TAOCP 4.6.3 Exercise 16
Section 4.6.3: Evaluation of Powers Exercise 16. [ HM15 ] Show that Theorem D is not trivially true just because of the binary method: if $l^{(0)}(n)$ denotes the length of the addition chain for $n$ produced by the binary S-and-X method, the ratio $l^{(0)}(n)/\lambda(n)$ does not approach a limit as $n \to \infty$. Verified: no Solve time: 7m04s Solution Let $l^{(0)}(n)$ denote the length of the addition chain for $n$...
TAOCP 3.5 Exercise 4
Section 3.5: What Is a Random Sequence? Exercise 4. ▶ [ HM14 ] Prove that $\Pr(S(n)$ and $T(n)) + \Pr(S(n)$ or $T(n)) = \Pr(S(n)) + \Pr(T(n))$, when $S$ and $T$ are any two statements and at least one of the limits exist. For example, if a sequence is 2-distributed, we would find that $$\Pr(u_n \le U_n < v_1 \text{ or } u_2 \le U_{n+1} < v_2) = v_1 - u_1...
TAOCP 3.4.1 Exercise 9
Section 3.4.1: Numerical Distributions Exercise 9. [ HM10 ] Why is the curve $f(x)$ of Fig. 9 concave for $x < 1$, convex for $x > 1$? Verified: no Solve time: 5m03s Solution To determine why the curve $f(x)$ is concave for $x < 1$ and convex for $x > 1$, we analyze its second derivative. Let $f(x)$ be the function shown in Fig. 9. Concavity and convexity are determined...
TAOCP 1.2.9 Exercise 6
Section 1.2.9: Generating Functions Exercise 6. [ HM15 ] Find the generating function for $$ \left\langle \sum_{0<k<n} \frac{1}{k(n-k)} \right\rangle; $$ differentiate it and express the coefficients in terms of harmonic numbers. Verified: yes Solve time: 1m37s Solution Let $$ a_n=\sum_{0<k<n}\frac{1}{k(n-k)} \qquad (n\ge 1), $$ and $a_0=0$. For $n\ge 1$, $$ \frac{1}{k(n-k)}=\frac{1}{n}\left(\frac{1}{k}+\frac{1}{n-k}\right), $$ since $$ \frac{1}{k}+\frac{1}{n-k}=\frac{n}{k(n-k)}. $$ Hence $$ a_n=\frac{1}{n}\sum_{k=1}^{n-1}\left(\frac{1}{k}+\frac{1}{n-k}\right) =\frac{1}{n}\left(2\sum_{k=1}^{n-1}\frac{1}{k}\right) =\frac{2H_{n-1}}{n}. $$ Define the generating function $$ A(z)=\sum_{n\ge 0} a_n...
TAOCP 1.2.8 Exercise 6
Section 1.2.8: Fibonacci Numbers Exercise 6. [ HM10 ] Prove Eq. (5). Verified: yes Solve time: 1m25s Let $$ A=\begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix}. $$ The Fibonacci sequence satisfies $F_{n+2}=F_{n+1}+F_n$ with initial values $F_0=0$, $F_1=1$. The claim is that $$ A^n= \begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix} $$ for every positive integer $n$. For $n=1$, one has $$ A^1=\begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix}...
TAOCP 1.2.6 Exercise 52
Section 1.2.6: Binomial Coefficients Exercise 52. [ HM11 ] Prove that Abel's binomial formula (16) is not always valid when $n$ is not a nonnegative integer, by evaluating the right-hand side when $n=x=-1$, $y=z=1$. Verified: yes Solve time: 3m56s Abel’s binomial formula (TAOCP 1.2.6 (16)) is stated for integers $n \ge 0$ as $$ (x+y)^n \sum_{k=0}^{n} \binom{n}{k}, x,(x-kz)^{k-1},(y+kz)^{n-k}. $$ We test the substitution $$ n=x=-1,\qquad y=z=1. $$ 1. Correct interpretation...
TAOCP 1.2.6 Exercise 42
Section 1.2.6: Binomial Coefficients Exercise 42. [ HM10 ] Express the binomial coefficient $\binom{r}{k}$ in terms of the beta function. Verified: yes Solve time: 1m07s From the factorial representation (5), $$ \binom{r}{k}=\frac{\Gamma(r+1)}{\Gamma(k+1)\Gamma(r-k+1)}. $$ Using the identity $\Gamma(r+2)=(r+1)\Gamma(r+1)$ and the beta function formula $B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$, we obtain $$ B(k+1,r-k+1)=\frac{\Gamma(k+1)\Gamma(r-k+1)}{\Gamma(r+2)}. $$ Taking reciprocals, $$ \frac{1}{B(k+1,r-k+1)}=\frac{\Gamma(r+2)}{\Gamma(k+1)\Gamma(r-k+1)}=(r+1)\frac{\Gamma(r+1)}{\Gamma(k+1)\Gamma(r-k+1)}. $$ Hence, $$ \binom{r}{k}=\frac{1}{r+1}\cdot \frac{1}{B(k+1,r-k+1)}. $$ Equivalently, using the integral definition of $B$, $$ \binom{r}{k}=\frac{1}{r+1}\left(\int_0^1 t^{k}(1-t)^{r-k},dt\right)^{-1}. $$ This...
TAOCP 1.2.11.3 Exercise 4
Section 1.2.11.3: Some Asymptotic Calculations Exercise 4. [ HM10 ] Prove Eq. (13). Verified: yes Solve time: 1m56s From the definition, $$ v = u - \ln(1+u). $$ Using the Taylor expansion valid for $|u|<1$, $$ \ln(1+u) = u - \frac{u^2}{2} + \frac{u^3}{3} - \frac{u^4}{4} + \cdots = \sum_{k\ge 1} \frac{(-1)^{k+1}u^k}{k}, $$ we substitute into the definition of $v$ to obtain cancellation of the linear term: $$ v = u...