#hm-simple
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: 2m06s Correctness The proposed solution does not answer Exercise 3.4.1.4. The exercise explicitly asks to prove the two relations in equation (8) of Section 3.4.1, which describe the distribution functions of $\max(X_1, X_2)$ and $\min(X_1, X_2)$ in terms of...
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: no Solve time: - Solution Let us denote the sequence in question by $$ a_n = \sum_{0<k<n} \frac{1}{k(n-k)}, \qquad n \ge 2, $$ and $a_0=a_1=0$. We first simplify the general term. Observe that $$ \frac{1}{k(n-k)} = \frac{1}{n} \left(...
TAOCP 1.2.8 Exercise 6
Section 1.2.8: Fibonacci Numbers Exercise 6. [ HM10 ] Prove Eq. (5). Verified: yes Solve time: 36s Let $$ A=\begin{pmatrix} 1&1\ 1&0 \end{pmatrix}. $$ The proof is by induction on $n$. For $n=1$, $$ A^1= \begin{pmatrix} 1&1\ 1&0 \end{pmatrix} = \begin{pmatrix} F_2&F_1\ F_1&F_0 \end{pmatrix}, $$ since $F_0=0$, $F_1=1$, and $F_2=1$. Thus Eq. (5) holds for $n=1$. Assume that $$ A^n= \begin{pmatrix} F_{n+1}&F_n\ F_n&F_{n-1} \end{pmatrix}. $$ Then $$ A^{n+1} = A^nA...
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: no Solve time: - Solution Abel's binomial formula (16) states that $$ (x+y)^n = \sum_k \binom{n}{k}x(x-kz)^{k-1}(y+kz)^{n-k}. \tag{16} $$ Take $$ n=-1,\qquad x=-1,\qquad y=1,\qquad z=1. $$ The left-hand side becomes $$ (x+y)^n = (-1+1)^{-1} = 0^{-1},...
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: no Solve time: - By Exercise 40(3), $$ B(k+1,r-k+1) =\frac{(r+1)!}{k!(r-k)!},B(r+1,1). $$ Since Exercise 40(1) gives $B(r+1,1)=1/(r+1)$, we obtain $$ B(k+1,r-k+1) =\frac{r!}{k!(r-k)!}. $$ Therefore, by Eq. (5), $$ \binom{r}{k} =\frac{r!}{k!(r-k)!} =\frac{1}{B(k+1,r-k+1)}, \qquad \text{integer } r \ge k \ge 0. $$ Hence $$ \boxed{\binom{r}{k}=\frac{1}{B(k+1,r-k+1)}}. $$
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: 1m21s Corrected Solution to Exercise 1.2.11.3.4, Part 4 We are asked to prove Eq. (13), which is $$ v = u - \ln(1+u). \tag{13} $$ Solution Define the function $$ f(u) = u - \ln(1+u). $$ We aim to show that this function has the properties asserted in Eq. (13). In particular, Eq....