#math-simple
TAOCP 4.6.4 Exercise 5
Section 4.6.4: Evaluation of Polynomials Exercise 5. [ M15 ] Count the number of multiplications and additions required by the second-order rule (4). Verified: yes Solve time: 2m28s Solution Let $$ u(x)=u_nx^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0 . $$ The second-order rule (4) groups terms in pairs and rewrites the polynomial in the nested form $$ u(x)= \bigl(\cdots((u_nx+u_{n-1})x+u_{n-2})x+\cdots\bigr), $$ with the nesting carried out two powers at a time. Equivalently, if we set $$ y=x^2,...
TAOCP 4.6.3 Exercise 15
Section 4.6.3: Evaluation of Powers Exercise 15. [ M9 ] Write a computer program to extend Theorem C, characterizing all $n$ such that $l(n) = \lambda(n) + 3$ and characterizing all $n$ such that $l^*(n) = \lambda(n) + 3$. Verified: no Solve time: 4m27s The reviewer's objections are correct. The previous answer does not solve the exercise, because it never produces the required characterization. A corrected solution must distinguish between...
TAOCP 4.6.3 Exercise 12
Section 4.6.3: Evaluation of Powers Exercise 12. [ M10 ] Is it possible to extend the tree shown in Fig. 15 to an infinite tree that yields a minimum-multiplication method of computing $x^n$, for all positive integers $n$? Verified: yes Solve time: 1m27s No, it is not possible to extend the tree of Fig. 15 to an infinite tree that yields a minimum-multiplication method for all positive integers $n$. For...
TAOCP 4.6.1 Exercise 7
Section 4.6.1: Division of Polynomials Exercise 7. [ M10 ] What are the units in the domain of all polynomials over a unique factorization domain? Verified: yes Solve time: 1m54s Let $S$ be a unique factorization domain, and let $f(x)\in S[x]$ be a unit. Then there exists $g(x)\in S[x]$ such that $$ f(x)g(x)=1. $$ Taking degrees gives $$ \deg(f)+\deg(g)=\deg(1)=0, $$ since property (i) of a unique factorization domain implies that...
TAOCP 4.3.3 Exercise 14
Section 4.3.3: How Fast Can We Multiply? Exercise 14. [ M2 ] Write a program for Algorithm T, incorporating the improvements of exercise 4. Compare it with a program for Algorithm 4.3.1M and with a program based on (2), to see how large $n$ must be before Algorithm T is an improvement. Verified: no Solve time: 8m16s Exercise 4.3.3.14 [M2] Algorithm T is Knuth's Toom-Cook multiplication algorithm. The purpose of...
TAOCP 4.3.3 Exercise 9
Section 4.3.3: How Fast Can We Multiply? Exercise 9. [ M15 ] Suppose the Fourier transformation method of the text is applied with all occurrences of $\omega$ replaced by $\omega^q$, where $q$ is some fixed integer. Find a simple relation between the numbers $(\hat{u}_0, \hat{u} 1, \ldots, \hat{u} {k-1})$ obtained by this general procedure and the numbers $(\hat{u}_0, \hat{u} 1, \ldots, \hat{u} {k-1})$ obtained when $q = 1$. Verified: yes...
TAOCP 4.3.2 Exercise 12
Section 4.3.2: Modular Arithmetic Exercise 12. [ M10 ] Prove that, if $0 \le u, v < m$, the modular addition of $u$ and $v$ causes overflow (lies outside the range allowed by the modular representation) if and only if the sum is less than $u$. (Thus the overflow detection problem is equivalent to the comparison problem.) Verified: yes Solve time: 1m50s Suppose $0 \le u, v < m$, and...
TAOCP 4.2.4 Exercise 11
Section 4.2.4: Distribution of Floating Point Numbers Exercise 11. [ M15 ] Given that $U$ is a random variable distributed according to the logarithmic law, prove that $1/U$ is also. Verified: yes Solve time: 3m09s Solution Let $V=1/U$. We will show that $V$ satisfies the same logarithmic law as $U$. By the characterization proved in Section 4.2.4, a positive random variable has the logarithmic law if and only if $$...
TAOCP 3.5 Exercise 11
Section 3.5: What Is a Random Sequence? Exercise 11. [ M10 ] Use Theorem C to prove that if a sequence $(U_n)$ is $\infty$-distributed, so is the subsequence $(U_{2n})$. Verified: no Solve time: 3m43s Exercise 3.5.11 [ M10 ] Let $(U_n)$ be $\infty$-distributed. By definition, $(U_n)$ is $m$-distributed for every positive integer $m$. To prove that $(U_{2n})$ is $\infty$-distributed, it suffices to show that it is $k$-distributed for every positive...
TAOCP 3.5 Exercise 8
Section 3.5: What Is a Random Sequence? Exercise 8. [ M15 ] Prove (13). Verified: yes Solve time: 1m24s Solution Assume that the sequence $\langle U_n\rangle$ is $(m,k)$-distributed, and let $d$ be a divisor of $m$. Write $$ m=rd. $$ We must prove that $\langle U_n\rangle$ is $(d,k)$-distributed. Fix real numbers $u_t,v_t$ with $0\le u_t<v_t\le1$ for $1\le t\le k$, and fix an integer $j$ with $0\le j<d$. Let $S(n)$ be...
TAOCP 3.4.2 Exercise 1
Section 3.4.2: Random Sampling and Shuffling Exercise 1. [ M12 ] Explain Eq. (1). Verified: yes Solve time: 1m46s Solution Equation (1) in Section 3.4.2 gives the probability with which the $(t+1)$st record of a file should be selected in Algorithm S, in order to maintain a uniform sample of size $n$ from the first $t+1$ records. Specifically, the probability that the new record is chosen to replace an element...
TAOCP 3.4.1 Exercise 8
Section 3.4.1: Numerical Distributions Exercise 8. [ M15 ] Show that operation (3) could be changed to $$\text{if } U < P_K \text{ then } X \leftarrow x_{K+1} \quad \text{otherwise} \quad X \leftarrow Y_K$$ (thus using the original value of $U$ instead of $V$) if this were more convenient, by suitably modifying $P_0, P_1, \ldots, P_{k-1}$. Verified: yes Solve time: 1m20s Solution We are asked to show that the alias...
TAOCP 3.3.2 Exercise 4
Section 3.3.2: Empirical Tests Exercise 4. [ M12 ] Prove that the probabilities in (4) are correct for the gap test. Verified: yes Solve time: 4m39s Solution Let $$ p=\beta-\alpha . $$ For a random sequence, each value $U_j$ is independently distributed on $[0,1)$, hence $$ \Pr(\alpha \le U_j < \beta)=p, \qquad \Pr(U_j<\alpha \text{ or } U_j\ge\beta)=1-p. $$ A gap of length $r$ is defined to be a subsequence $$...
TAOCP 3.2.1 Exercise 3
Section 3.2.1: The Linear Congruential Method Exercise 3. [ M10 ] If $a$ and $m$ are not relatively prime, explain why the sequence will be somewhat handicapped and probably not very random; hence we will generally want the multiplier $a$ to be relatively prime to the modulus $m$. Verified: yes Solve time: 2m43s Corrected Solution for Exercise 3.2.1.3 [ M10 ] Let the linear congruential generator (LCG) be defined by...
TAOCP 1.3.3 Exercise 16
Section 1.3.3: Applications to Permutations Exercise 16. [ M15 ] Start with the permutation 1324 in linear notation; convert it to canonical cycle form and then remove the parentheses; repeat this process until arriving at the original permutation. What permutations occur during this process? Verified: yes Solve time: 32m02s Solution Let the initial permutation in linear notation be $1324$. This means the mapping on ${1,2,3,4}$ is $$ 1 \mapsto 1,\quad...
TAOCP 1.3.3 Exercise 15
Section 1.3.3: Applications to Permutations Exercise 15. [ M12 ] Is there a permutation that represents exactly the same transformation both in the canonical cycle form without parentheses and in the linear form? Verified: no Solve time: 4m13s Solution Yes. The identity permutation is the unique example. Let $\pi$ be a permutation of ${1,2,\ldots,n}$. Write its canonical cycle form as $$ (c_{11}\ c_{12}\ \cdots\ c_{1\ell_1}) (c_{21}\ c_{22}\ \cdots\ c_{2\ell_2}) \cdots...
TAOCP 1.3.1 Exercise 7
Section 1.3.1: Description of MIX Exercise 7. [ M15 ] Give a precise definition of the results of the DIV instruction for all cases in which overflow does not occur, using the algebraic operations X mod Y and \lfloor X/Y \rfloor . Verified: yes Solve time: 9m36s Let $D$ be the signed integer formed from $(rA,rX)$, and let $m\neq 0$ be the signed integer in $M$. Assume no overflow occurs,...
TAOCP 1.3.3 Exercise 5
Section 1.3.3: Applications to Permutations Exercise 5. [ M10 ] Equation (3) shows several equivalent ways to express the same permutation in cycle form. How many different ways of writing that permutation are possible, if all singleton cycles are suppressed? Verified: yes Solve time: 1m14s Kí hiệu phép hoán vị đã cho là $(acf)(bd)$, trong đó $e$ là điểm bất động và bị lược bỏ trong ký hiệu chu trình....
TAOCP 1.2.9 Exercise 9
Section 1.2.9: Generating Functions Exercise 9. [ M11 ] In the notation of Eqs. (34) and (35), what is $h_4$ in terms of $S_1,S_2,S_3,$ and $S_4$? Verified: yes Solve time: 2m41s Solution We are asked to express $h_4$ in terms of the elementary symmetric functions $S_1, S_2, S_3, S_4$, using the notation of Eqs. (34) and (35). In Section 1.2.9, the $h_n$ denote the complete homogeneous symmetric functions, and $S_n$...
TAOCP 1.2.9 Exercise 1
Section 1.2.9: Generating Functions Exercise 1. [ M12 ] What is the generating function for the sequence $2,5,13,35,\ldots = \langle 2^n+3^n \rangle$? Verified: no Solve time: - Solution Let $G(z)$ be the generating function for the sequence $$ \langle 2^n+3^n\rangle = 2,5,13,35,\ldots. $$ By definition, $$ G(z)=\sum_{n\ge0}(2^n+3^n)z^n. $$ Using operation A, Eq. (2), we split this into two generating functions: $$ G(z)=\sum_{n\ge0}2^nz^n+\sum_{n\ge0}3^nz^n. $$ Since $$ 2^nz^n=(2z)^n, \qquad 3^nz^n=(3z)^n, $$ Eq....
TAOCP 1.2.9 Exercise 2
Section 1.2.9: Generating Functions Exercise 2. [ M13 ] Prove Eq. (11). Verified: no Solve time: - Solution We are asked to prove equation (11): $$ \left(\frac{a_0}{0!}+\frac{a_1}{1!}z+\frac{a_2}{2!}z^2+\cdots\right) \left(\frac{b_0}{0!}+\frac{b_1}{1!}z+\frac{b_2}{2!}z^2+\cdots\right) = \left(\frac{c_0}{0!}+\frac{c_1}{1!}z+\frac{c_2}{2!}z^2+\cdots\right), $$ where $c_n = \sum_k \binom{n}{k} a_k b_{n-k}$. Let $$ A(z) = \sum_{k \ge 0} \frac{a_k}{k!} z^k, \qquad B(z) = \sum_{k \ge 0} \frac{b_k}{k!} z^k. $$ The product $A(z)B(z)$ is then $$ A(z)B(z) = \sum_{i \ge 0} \sum_{j \ge 0}...
TAOCP 1.2.9 Exercise 7
Section 1.2.9: Generating Functions Exercise 7. [ M15 ] Verify all the steps leading to Eq. (38). Verified: yes Solve time: 4m53s The verification of the steps leading to Eq. (38) concerns a standard chain of manipulations in Section 1.2.9: algebraic expansion of sums, reindexing, and interchange of finite summations. The correct approach is to check each transformation for (i) validity of index changes, (ii) preservation of summation ranges, and...
TAOCP 1.2.9 Exercise 4
Section 1.2.9: Generating Functions Exercise 4. [ M01 ] Explain why Eq. (19) is a special case of Eq. (21). Verified: no Solve time: - Equation (21) states that if $x^{t+1}=x^t+z$ and $x=1$ when $z=0$, then $$ x^r=\sum_{k\ge0}\binom{r-kt}{k}\frac{r}{r-kt}z^k. $$ Take $t=-1$. Then the defining equation becomes $$ x^{0}=x^{-1}+z, $$ hence $$ 1=\frac1x+z, \qquad\text{so}\qquad x=\frac1{1-z}. $$ Therefore $$ x^r=(1-z)^{-r}. $$ Substituting $t=-1$ into Eq. (21) gives $$ (1-z)^{-r} =\sum_{k\ge0}\binom{r+k}{k}\frac{r}{r+k}z^k. $$ Since...
TAOCP 1.2.7 Exercise 12
Section 1.2.7: Harmonic Numbers Exercise 12. [ M10 ] Evaluate $H_{\infty}^{(1000)}$ correct to at least 100 decimal places. Verified: no Solve time: - By the definition of generalized harmonic numbers, $$ H_{\infty}^{(1000)}=\sum_{k=1}^{\infty}\frac1{k^{1000}}=\zeta(1000). $$ For even integers, Euler's formula gives $$ \zeta(2m)=\frac{(-1)^{m+1}B_{2m}(2\pi)^{2m}}{2(2m)!}. $$ In the present case, direct numerical evaluation is simpler. Since $$ \sum_{k=2}^{\infty}\frac1{k^{1000}} <\sum_{k=2}^{\infty}\frac1{2^{1000}}\frac1{2^{k-2}} =\frac1{2^{999}}, $$ the tail beyond the first term is less than $10^{-300}$. Hence the decimal...
TAOCP 1.2.7 Exercise 6
Section 1.2.7: Harmonic Numbers Exercise 6. [ M15 ] Prove that the harmonic numbers are directly related to Stirling's numbers, which were introduced in the previous section; in fact, $$ H_n = \left[{n+1 \atop 2}\right] / n!. $$ Verified: no Solve time: - Solution We wish to prove that $$ H_n = \frac{\left[{,n+1 \atop 2,}\right]}{n!}, $$ where $\left[{n \atop k}\right]$ denotes the Stirling numbers of the first kind, as defined...
TAOCP 1.2.6 Exercise 21
Section 1.2.6: Binomial Coefficients Exercise 21. [ M05 ] Both sides of Eq. (25) are polynomials in $s$; why isn't that equation an identity in $s$? Verified: yes Solve time: 34s In Eq. (25), if $m$, $n$, and $r$ are regarded as fixed nonnegative integers, each term $\binom{s+k}{n}$ is a polynomial in $s$ of degree $n$ by Eq. (3). Hence the left-hand side is a polynomial in $s$ of degree...
TAOCP 1.2.6 Exercise 39
Section 1.2.6: Binomial Coefficients Exercise 39. [ M10 ] What is the sum $\sum_k \left[{n \atop k}\right]$ of the numbers in each row of Stirling's first triangle? What is the sum of these numbers with alternating signs? Verified: no Solve time: - Let $\left[{n \atop k}\right]$ denote the numbers in Stirling's first triangle. By the interpretation of $\left[{n \atop k}\right]$ as the number of permutations of $n$ elements having exactly...
TAOCP 1.2.6 Exercise 18
Section 1.2.6: Binomial Coefficients Exercise 18. [ M15 ] Prove Eq. (22) using Eqs. (21) and (6). Verified: yes Solve time: 34s Solution Equation (22) states that for integers $n \ge 0$ and $m \ge 0$: $$ \sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}. $$ We are to prove this using Eq. (21) and the symmetry relation (6). Equation (21) is the more general summation formula $$ \sum_{k=0}^{n} \binom{r+k}{k} = \binom{r+n+1}{n}, \qquad \text{integer...
TAOCP 1.2.6 Exercise 24
Section 1.2.6: Binomial Coefficients Exercise 24. [ M15 ] Explain why the results of the previous two exercises combine to give a proof of Eq. (26). Verified: no Solve time: 1m30s Solution Exercise 22 proves Eq. (26) for all quadruples $(r,s,t,n)$ satisfying $$ s=(n-1)r+nt. $$ Exercise 23 proves the following induction step: If Eq. (26) holds for $(r,s,t,n)$ and for $(r,s-t,t,n-1)$, then it also holds for $(r,s+1,t,n)$. Fix $r,t,n$, and...
TAOCP 1.2.6 Exercise 36
Section 1.2.6: Binomial Coefficients Exercise 36. [ M10 ] What is the sum $\sum_k \binom{n}{k}$ of the numbers in each row of Pascal's triangle? What is the sum of these numbers with alternating signs, $\sum_k \binom{n}{k}(-1)^k$? Verified: no Solve time: - By the binomial theorem (13), with $x=y=1$, $$ (1+1)^n = \sum_k \binom{n}{k}1^k1^{n-k} = \sum_k \binom{n}{k}. $$ Hence $$ \sum_k \binom{n}{k} = 2^n. $$ Similarly, with $x=-1$ and $y=1$, $$...
TAOCP 1.2.6 Exercise 23
Section 1.2.6: Binomial Coefficients Exercise 23. [ M13 ] Assuming that Eq. (26) holds for $(r,s,t,n)$ and $(r,s-t,t,n-1)$, prove it for $(r,s+1,t,n)$. Verified: yes Solve time: 33s Solution Equation (26) is the identity $$ \sum_k \binom{r}{m+k}\binom{s}{n-k}\binom{k}{t} = \binom{r+s-t}{m+n-t}\binom{r}{m+t}, $$ where the summation extends over all integers $k$. Assume that Eq. (26) holds for $(r,s,t,n)$ and also for $(r,s-t,t,n-1)$. We must prove it for $(r,s+1,t,n)$. Consider $$ \sum_k \binom{r}{m+k}\binom{s+1}{n-k}\binom{k}{t}. $$ By...
TAOCP 1.2.6 Exercise 15
Section 1.2.6: Binomial Coefficients Exercise 15. [ M15 ] Prove the binomial formula, Eq. (13). Verified: yes Solve time: 42s Solution We prove Eq. (13) by induction on $r$. When $r=0$, the right-hand side contains only the term with $k=0$, since $\binom{0}{k}=0$ for $k\ne0$. Therefore $$ \sum_k \binom{0}{k}x^ky^{-k} = \binom{0}{0} = 1 = (x+y)^0. $$ Hence Eq. (13) is true for $r=0$. Assume that $$ (x+y)^r=\sum_k\binom{r}{k}x^ky^{r-k}, \qquad r\ge0. $$ Then...
TAOCP 1.2.6 Exercise 16
Section 1.2.6: Binomial Coefficients Exercise 16. [ M15 ] Given that $n$ and $k$ are positive integers, prove the symmetrical identity $$ (-1)^n\binom{-n}{k-1} = (-1)^k\binom{-k}{n-1}. $$ Verified: yes Solve time: 34s Solution We begin with the left-hand side of the identity and apply the definition (3) of binomial coefficients for general integers $r$: $$ \binom{-n}{k-1} = \frac{(-n)(-n-1)\cdots(-n-(k-2))}{(k-1)!}. $$ Expanding the numerator, we have $$ (-n)(-n-1)\cdots(-n-(k-2)) = (-1)^{k-1} n(n+1)\cdots(n+k-2), $$ because...
TAOCP 1.2.6 Exercise 37
Section 1.2.6: Binomial Coefficients Exercise 37. [ M10 ] From the answers to the preceding exercise, deduce the value of the sum of every other entry in a row, $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots$. Verified: no Solve time: - By Exercise 36 and the binomial theorem (13), $$ \sum_k \binom{n}{k} = (1+1)^n = 2^n, $$ and $$ \sum_k \binom{n}{k}(-1)^k = (1-1)^n = 0 \qquad (n>0). $$ Let $$...
TAOCP 1.2.6 Exercise 13
Section 1.2.6: Binomial Coefficients Exercise 13. [ M13 ] Prove the summation formula, Eq. (10). Verified: yes Solve time: 38s Solution Equation (10) states that $$ \sum_{k=0}^{n}\binom{r+k}{k} = \binom{r+n+1}{n}, \qquad \text{integer } n\ge 0. $$ We prove this formula by induction on $n$. When $n=0$, the left-hand side is $$ \sum_{k=0}^{0}\binom{r+k}{k} = \binom{r}{0} = 1 $$ by equation (4). The right-hand side is $$ \binom{r+0+1}{0} = \binom{r+1}{0} = 1. $$...
TAOCP 1.2.4 Exercise 26
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 26. [ M15 ] Let $p$ be an odd prime number, let $a$ be any integer, and let $b = a^{(p-1)/2}$. Show that $b \bmod p$ is either 0 or 1 or $p-1$. [Hint: Consider $(b+1)(b-1)$.] Verified: yes Solve time: 1m03s Solution Let $p$ be an odd prime, $a$ any integer, and define $b = a^{(p-1)/2}.$ We are asked to show...
TAOCP 1.2.4 Exercise 27
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 27. [ M15 ] Given that $n$ is a positive integer, let $\varphi(n)$ be the number of values among ${0,1,\ldots,n-1}$ that are relatively prime to $n$. Thus $\varphi(1)=1$, $\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=2$, etc. Show that $\varphi(p)=p-1$ if $p$ is a prime number; and evaluate $\varphi(p^e)$, when $e$ is a positive integer. Verified: yes Solve time: 34s Solution Let $p$ be a prime...
TAOCP 1.2.4 Exercise 22
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 22. ▶ [ M10 ] Give an example to show that Law B is not always true if $a$ is not relatively prime to $m$. Verified: yes Solve time: 3m11s Take $m=6$ and $a=2$. Since $2$ and $6$ are not relatively prime, Law B need not hold. Let $x=1$ and $y=4$. Then $$ ax=2\cdot1=2,\qquad ay=2\cdot4=8\equiv2\pmod6, $$ so $$ ax\equiv ay\pmod6. $$...
TAOCP 1.2.4 Exercise 25
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 25. [ M02 ] Show that, according to Theorem F, $a^{p-1} \bmod p = [a \text{ is not a multiple of } p]$ whenever $p$ is a prime number. Verified: yes Solve time: 1m18s By Theorem F, if $p$ is prime then $$ a^p \equiv a \pmod p. $$ If $a$ is not a multiple of $p$, then $a \perp p$...
TAOCP 1.2.4 Exercise 23
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 23. [ M10 ] Give an example to show that Law D is not always true if $r$ is not relatively prime to $s$. Verified: no Solve time: 33s Consider integers $a=2$, $b=8$, $r=4$, and $s=6$. Here $r$ and $s$ are not relatively prime since $\gcd(4,6)=2>1$. We examine the congruences modulo $r$ and $s$: Modulo $r=4$, we have $a \equiv b...
TAOCP 1.2.4 Exercise 4
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 4. ▶ [ M10 ] Using the previous exercise, prove that $\lfloor -x \rfloor = -\lceil x \rceil$. Verified: yes Solve time: 3m10s Let $n=\lceil x\rceil$. By the defining property of the ceiling function, $n$ is the least integer greater than or equal to $x$. Equivalently, $$ n-1 < x \le n. $$ Multiply every part of this inequality by $-1$....
TAOCP 1.2.4 Exercise 19
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 19. ▶ [ M10 ] ( Law of inverses. ) If $n \perp m$, there is an integer $n'$ such that $nn' \equiv 1$ (modulo $m$). Prove this, using the extension of Euclid’s algorithm (Algorithm 1.2.1E). Verified: yes Solve time: 30s Since $n \perp m$, the extended Euclidean algorithm (Algorithm 1.2.1E) produces integers $u$ and $v$ such that $un + vm...
TAOCP 1.2.4 Exercise 20
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 20. [ M15 ] Use the law of inverses and Law A to prove Law B. Verified: yes Solve time: 2m23s Solution Assume that $$ ax \equiv by \pmod m, \qquad a \equiv b \pmod m, \qquad a \perp m. $$ We must prove that $$ x \equiv y \pmod m. $$ Since $a \perp m$, Exercise 19 (the law of...
TAOCP 1.2.4 Exercise 17
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 17. [ M15 ] Prove Law A directly from the definition of congruence, and also prove half of Law D: If $a \equiv b$ (modulo $rs$), then $a \equiv b$ (modulo $r$) and $a \equiv b$ (modulo $s$). (Here $r$ and $s$ are arbitrary integers.) Verified: yes Solve time: 30s Solution By definition of congruence, the statement $$ u \equiv v...
TAOCP 1.2.4 Exercise 7
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 7. [ M15 ] Show that $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x+y \rfloor$ and that equality holds if and only if $x \bmod 1 + y \bmod 1 < 1$. Does a similar formula hold for ceilings? Verified: no Solve time: 5m31s Solution Let $x$ and $y$ be arbitrary real numbers. By definition, $x = \lfloor x...
TAOCP 1.2.4 Exercise 3
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 3. [ M10 ] Let $n$ be an integer, and let $x$ be a real number. Prove that a) $\lfloor x \rfloor < n$ if and only if $x < n$; b) $n \le \lfloor x \rfloor$ if and only if $n \le x$; c) $\lfloor x \rfloor \le n$ if and only if $x < n+1$; d) $n < \lceil...
TAOCP 1.2.4 Exercise 18
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 18. [ M15 ] Using Law B, prove the other half of Law D: If $a \equiv b$ (modulo $r$) and $a \equiv b$ (modulo $s$), then $a \equiv b$ (modulo $rs$), provided that $r \perp s$. Verified: no Solve time: 32s Solution Assume $a \equiv b \pmod r$ and $a \equiv b \pmod s$, with $r \perp s$. By definition...
TAOCP 1.2.4 Exercise 16
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 16. [ M10 ] Assume that $y>0$. Show that if $(x-z)/y$ is an integer and if $0 \le z < y$, then $z = x \bmod y$. Verified: yes Solve time: 43s By definition (1), $$ x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor . $$ Hence $$ x-(x\bmod y) $$ is an integral multiple of $y$, by property (c). Since $(x-z)/y$ is...
TAOCP 1.2.10 Exercise 4
Section 1.2.10: Analysis of an Algorithm Exercise 4. [ M10 ] Give an explicit, closed formula for the values of $p_{nk}$ in the coin-tossing experiment, Eq. (17). Verified: yes Solve time: 1m10s From Eq. (17), the recurrence for the probabilities is $$ p_{nk}=p,p_{n-1,k-1}+q,p_{n-1,k}, $$ where $q=1-p$. The generating function therefore satisfies $$ G_n(z)=(q+pz)^n $$ by Eq. (18). Expanding this by the binomial theorem gives $$ G_n(z)=\sum_{k=0}^n \binom{n}{k} q^{,n-k}p^k z^k. $$...
TAOCP 1.2.11.2 Exercise 13
Section 1.2.11.2: Euler's Summation Formula Exercise 13. [ M10 ] Prove or disprove: $g(n)=\Omega(f(n))$ if and only if $f(n)=O(g(n))$. 1.2.11.2. Euler's summation formula. One of the most useful ways to obtain good approximations to a sum is an approach due to Leonhard Euler. His method approximates a finite sum by an integral, and gives us a means to get better and better approximations in many cases. Figure 12 shows a...
TAOCP 1.2.10 Exercise 11
Section 1.2.10: Analysis of an Algorithm Exercise 11. [ M15 ] What happens to the semi-invariants of a distribution if we change $G(z)$ to $F(z)=z^nG(z)$? Verified: yes Solve time: 4m02s Corrected Solution Let $$ G(z) = \sum_{k \ge 0} p_k z^k $$ be the probability generating function (pgf) of a discrete random variable $X$. The semi-invariants (cumulants) $\kappa_r$ of $X$ are defined by the expansion $$ \log G(z) = \sum_{r...
TAOCP 1.2.10 Exercise 5
Section 1.2.10: Analysis of an Algorithm Exercise 5. [ M13 ] What are the mean and standard deviation of the distribution in Fig. 11? Verified: yes Solve time: 35s Solution Figure 11 corresponds to the coin-tossing experiment of Eq. (18) with $n=12$ and $p=\frac35$. Hence $q=1-p=\frac25$. By Eq. (19), the mean number of heads is $$ pn=\frac35\cdot 12=\frac{36}{5}=7.2. $$ The variance is $$ pqn=\frac35\cdot\frac25\cdot 12 =\frac{72}{25}. $$ Therefore the standard...
TAOCP 1.2.11.2 Exercise 11
Section 1.2.11.2: Euler's Summation Formula Exercise 11. [ M11 ] Explain why Eq. (18) is true. Verified: yes Solve time: 44s Solution Equation (18) states $$ \sqrt[n]{n} = e^{\ln n/n} = 1 + \frac{\ln n}{n} + O!\Big((\ln n/n)^2\Big). $$ We justify this by applying the Taylor series for the exponential function at zero. Let $x = \ln n / n$. Then $x \to 0$ as $n \to \infty$. By the...
TAOCP 1.2.10 Exercise 3
Section 1.2.10: Analysis of an Algorithm Exercise 3. [ M15 ] What are the minimum, maximum, average, and standard deviation of the number of times step M4 is executed, if we are using Algorithm M to find the maximum of 1000 randomly ordered, distinct items? (Give your answer as decimal approximations to these quantities.) Verified: yes Solve time: 4m35s Let $X$ be the number of times step M4 is executed...