#hm-simple
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: yes Solve time: 1m25s Solution Let $l^{(0)}(n)$ denote the length of an 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: 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.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.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 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....