Graded: 5.2 #12, 5.3 #12
5.2 #4
a) $18 = 1(4)+2(7)$, $19 = 3(4)+1(7)$, $20 = 5(4)+0(7)$, $21 = 0(4)+3(7)$
b) Let $k\ge 21$. We assume that the numbers $18,19,20,\ldots,k-1,k$ can each be written in the form $4s+7t$ for some nonnegative integers $s,t$. (Alternatively, it suffices to assume that $k-3$ can be written in this form.)
c) We must show that $k+1$ can be written in the form $4s+7t$ for some nonnegative integers $s,t$.
d) Suppose $k\ge 21$ and assume the inductive hypothesis stated in (b). Then $k-3\ge 18$, so there are nonnegative integers $s,t$ such that $k-3=4s+7t$. It follows that $k+1=4s’+7t$, where $s’=s+1$.
e) Informal explanation (which is all that was expected here): We explicitly verified that 18, 19, 20, and 21 cents could be formed from 4- and 7-cent stamps. The inductive step shows that if a given amount can be formed from 4- and 7-cent stamps, then so can that amount plus 4 cents. Thus, having formed totals of 18 through 21 cents, the inductive step enables us to form totals of 22 through 25, which in turn enables us to form 26 through 29, and so on, reaching every integer greater than or equal to 18.
Alternatively, here’s a formal proof that this use of induction is valid: We argue by contradiction. Suppose there is an integer $n\ge 18$ that cannot be expressed as $4s+7t$ for $s,t\in\mathbb N$. In that case, consider the least such integer, $n_0$ (which exists thanks to the well-ordering principle). Then $n_0\ge 22$, because we explicitly dealt with 18, 19, 20, 21 in the basis step. Therefore, $n_0-4\ge 18$. Also, $n_0-4 < n_0$. Since $n_0-4$ is less than the least integer that isn’t of the form $4s+7t$, we conclude that $n_0-4$ is of that form. But then the inductive step shows that $n_0$ is of that form as well, which is a contradiction. So, in fact, there cannot be an integer $n\ge 18$ that is not of the form $4s+7t$ with $s,t\in\mathbb N$, i.e., we succeeded in proving that all integers $n\ge 18$ are of that form.
$\bigstar$ 5.2 #12
For the basis step, note that 1 can be written as a sum of distinct powers of two: $1=2^0$. (Perhaps it should have been clarified that a single power of two qualifies as a “sum”!)
For the inductive step, suppose the integers $1,2,\ldots,k$ can each be written as a sum of distinct powers of 2. We will infer that $k+1$ can also be written as a sum of distinct powers of two. We consider two cases: $k+1$ is odd or $k+1$ is even.
Case 1: Suppose $k+1$ is odd. Then $k$ is even. Let $$k=2^{a_1}+2^{a_2}+\cdots+2^{a_r},$$ where $a_1,\ldots,a_r$ are distinct integers (this is possible because of the inductive hypothesis). Then none of $a_1,\ldots,a_r$ can be 0, because that would make $k$ odd. So, $$k+1=2^{a_1}+2^{a_2}+\cdots+2^{a_r}+2^0$$ is a representation of $k+1$ as a sum of distinct powers of 2.
Case 2: Suppose $k+1$ is even. In that case, $\frac{k+1}2$ is an integer and an element of $\{1,2,\ldots,k\}$, so $$\frac{k+1}2=2^{a_1}+2^{a_2}+\cdots+2^{a_r}$$ for distinct integers $a_1,\ldots,a_r$. It follows that \begin{align*} k+1 &= 2(2^{a_1}+2^{a_2}+\cdots+2^{a_r}) \\ &= 2^{a_1+1}+2^{a_2+1}+\cdots+2^{a_r+1}, \end{align*} and this is a representation of $k+1$ as a sum of distinct powers of 2.
In either case, we have shown that $k+1$ is a sum of distinct powers of 2. This completes the inductive step; we conclude by strong induction that every positive integer can be written in that form. $\blacksquare$
Remarks. To see what is going on in this proof, it is instructive to think recursively. The proof provides a recipe for writing $k+1$ as a sum of distinct powers of 2 based on how some smaller integer is written as a sum of distinct powers of 2. Thus, if we wanted to write 21 in that form, the proof would tell us to do 20 first, and 10 before that, and 5 before that, and 4 before that, and 2 before that, and 1 before that. We know $1=2^0$. Adding 1 to the exponent gives $2=2^1$, then $4=2^2$. Tacking on $2^0$ gives $5=2^2+2^0$, and so on. This algorithm is in fact rather similar to how we converted integers to base $b$ in section 4.2.
Theorem 1 on page 246 of the book could be proven in a manner similar to the proof above (which establishes the case of $b=2$).
5.2 #14
We argue by strong induction. For the basis step, consider $n=1$. In this case, the initial state (one pile of $n$ stones) is the same as the end state ($n$ piles of one stone), so we don’t do anything and we don’t compute any products $rs$. Accordingly, the sum of the products computed is $0$, which does equal $\frac{n(n-1)}2$.
For the inductive step, suppose the proposition is true for $n=1,2,\ldots,k$. We will show that it is also true for $n=k+1$. Given that the initial number of stones is $k+1$, the first move splits the pile into two piles of size $r$ and $s$, where $r,s\le k$ and $r+s=k+1$. We now have two subproblems: the pile of $r$ stones must be broken down into $r$ piles of one stone each, and the pile of $s$ stones must be broken down into $s$ piles of one stone each. These subproblems fall under the scope of the inductive hypothesis. So, the total of the products computed in the course of resolving the subproblems is $\frac{r(r-1)}2+\frac{s(s-1)}2$. To this we add the product computed after our first move, which is $rs$. The total is $\frac{r(r-1)}2+\frac{s(s-1)}2+rs = \frac{r^2+2rs+s^2-r-s}2 = \frac{(r+s)(r+s-1)}2 = \frac{(k+1)(k+1-1)}2$. This is what we aimed to show in the inductive step.
Thus, by strong induction, the proposition is shown to be true for any initial number of stones $n\ge 1$. $\blacksquare$
Remark. There is also a non-inductive, combinatorial proof which establishes why the answer is $\binom n2$. This is left as a puzzle to the reader.
$\bigstar$ 5.3 #12
We argue by induction. For the basis step, consider $n=1$. Then the assertion is that $f_1^2=f_1f_2$. This is true (both sides are equal to 1).
For the inductive step, suppose $$f_1^2+f_2^2+\cdots+f_k^2 = f_kf_{k+1}.$$ Then, by adding $f_{k+1}^2$ to both sides and applying the Fibonacci recurrence, we have \begin{align*} f_1^2+f_2^2+\cdots+f_k^2+f_{k+1}^2 &= f_kf_{k+1} + f_{k+1}^2 \\ &= f_{k+1}(f_k+f_{k+1}) \\ &= f_{k+1}f_{k+2}. \end{align*} We conclude by mathematical induction that the identity holds for all integers $n\ge 1$.
5.3 #48-52
#48: $A(1,0)=0$, $A(0,1)=2$, $A(1,1)=2$, $A(2,2)=4$
#49: We argue by induction. Basis step: $A(1,2)=A(0,A(1,1))=A(0,2)=4$. Inductive step: Suppose $A(k,2)=4$, where $k\ge 1$. Then $A(k+1,2)=A(k,A(k+1,1))=A(k,2)=4$. We conclude that $A(m,2)=4$ for all $m\ge 1$.
#50: We argue by induction. Basis step: $A(1,1)=2=2^1$. Inductive step: Suppose $A(1,k)=2^k$, where $k\ge 1$. Then $A(1,k+1)=A(0,A(1,k))=A(0,2^k)=2\cdot 2^k=2^{k+1}$. We conclude that $A(1,n)=2^n$ for all $n\ge 1$.
#51: $A(2,3)=A(1,A(2,2))=A(1,4)=16$
$A(3,3)=A(2,A(3,2))=A(2,4)=A(1,A(2,3))=A(1,16)=2^{16}$
#52: To start, $A(3,4)=A(2,A(3,3))=A(2,2^{16})$.
Now we note that, for any $n\ge 2$, we have $A(2,n)=A(1,A(2,n-1))=2^{A(2,n-1)}$. Thus we have the following pattern: \begin{align*} A(2,1)&=2 \\ A(2,2)&=2^2 \\ A(2,3)&=2^{2^2} \\ A(2,4)&=2^{2^{2^2}} \\ &\vdots \end{align*} (where each tower of exponents is evaluated from the top down). So, $A(2,2^{16})$ is the unspeakably huge number $$2^{2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}}$$ where there are $2^{16}$ 2′s in the tower.
6.1 #16
There are $26^4$ strings of four lowercase letters, of which $25^4$ do not contain the letter x. Thus $26^4-25^4 = \boxed{66351}$ strings of four lowercase letters do contain the letter x.
6.1 #22
To solve (a)-(f), let $X$ be the set of positive integers less than 1000 that are multiples of 7, and let $Y$ be the set of positive integers less than 1000 that are multiples of 11. Note that $X\cap Y$ is the set of positive integers less than 1000 that are multiples of 77.
In general, the number of integers in the set $\{1,2,3,\ldots,N\}$ that are multiples of $k$ is $\left\lfloor \frac Nk \right\rfloor$. Thus $|X|=\left\lfloor \frac{999}7\right\rfloor = 142$, $|Y|=\left\lfloor \frac{999}{11} \right\rfloor = 90$, and $|X\cap Y|=\left\lfloor \frac{999}{77} \right\rfloor = 12$.
a) $|X| = 142$
b) $|X-Y| = |X|-|X\cap Y| = 130$
c) $|X\cap Y| = 12$
d) $|X\cup Y| = |X|+|Y|-|X\cap Y| = 220$
e) $|X\oplus Y| = |X\cup Y|-|X\cap Y| = 208$
f) $|\overline{X\cup Y}| = 999 – 220 = 779$
g) We consider integers with 1, 2, or 3 digits as separate cases. There are 9 positive integers of 1 digit. There are $9\cdot 9$ positive integers consisting of 2 distinct digits, because there are 9 choices for the first digit (1 through 9) and 9 choices for the second digit (0 through 9, except the digit already used). Similarly, there are $9\cdot 9\cdot 8$ positive integers consisting of 3 distinct digits.
Thus, the number of positive integers less than 1000 with distinct digits is $9+9\cdot 9+9\cdot 9\cdot 8 = 738$.
h) We consider two cases: integers that end in 0, and integers that end in any other even digit.
First case: We count integers that end in 0 by splitting them into subcases of 2 or 3 digits. There are 9 positive integers ending in 0 that consist of 2 distinct digits. There are $9\cdot 8$ positive integers ending in 0 that consist of 3 distinct digits (since we have 9 choices for the first digit and 8 choices for the second digit).
Second case: We count integers that end in 2, 4, 6, or 8 by splitting them into subcases of 1, 2, or 3 digits. There are 4 even positive integers of 1 digit. There are $4\cdot 8$ even positive integers of 2 distinct digits, because there are 4 choices for the second digit and then 8 choices for the first digit (can’t be 0, can’t be the digit already chosen). There are $4\cdot 8\cdot 8$ even positive integers of 3 distinct digits, because there are 4 choices for the last digit, then 8 choices for the first digit, then 8 choices for the middle digit.
Totaling up all our subcases, the number of even positive integers less than 1000 with distinct digits is $9+9\cdot 8+4+4\cdot 8+4\cdot 8\cdot 8 = 373$.
6.1 #32
a) $26^8$
b) $26\cdot 25\cdot 24\cdot ~\cdots~ \cdot 19$
c) $1\cdot 26^7$
d) $1\cdot 25\cdot 24\cdot ~\cdots~ \cdot 19$
e) $1\cdot 26^6\cdot 1$
f) $1^2\cdot 26^6$
g) $1^2\cdot 26^4\cdot 1^2$
h) $26^6 + 26^6 – 26^4 = (1351)(26^4)$
6.1 #35
To create a one-to-one function from a set of 5 elements to a set of $n$ elements, we must assign 5 images. There are $n$ choices for the first, $n-1$ for the second, and so forth, so the number of such functions is $n(n-1)(n-2)(n-3)(n-4)$. (Hence the answers in the back of the book.)
6.1 #50
First, we count strings of 10 bits that include five consecutive 0s. We break these down into cases according to where 00000 first appears.
Case 1: 00000xxxxx. There are $2^5$ strings of this type.
Case 2: 100000xxxx. Notice that the 1 is there to ensure that we don’t re-count strings from case 1. There are $2^4$ strings of this type.
Cases 3-6 are similar: x100000xxx, xx100000xx, xxx100000x, xxxx100000. Each case includes $2^4$ strings.
Adding up these cases, we have 112 strings of 10 bits that include five consecutive 0s.
By the same argument, we have 112 strings of 10 bits that include five consecutive 1s. But two of these (0000011111, 1111100000) were already counted as having five consecutive 0s. Thus, the number of 10-bit strings that contain either five consecutive 0s or five consecutive 1s is $112+112-2 = 222$.
6.2 #8
We argue by contradiction. Suppose $f$ is one-to-one. Let $S=\{s_1,s_2,\ldots,s_n\}$. Then $f(s_1),f(s_2),\ldots,f(s_n)$ are distinct elements of $T$, so $|T|\ge n$, that is, $|T|\ge |S|$. But it is given that $|S| > |T|$, so we have a contradiction. Therefore, $f$ cannot be one-to-one. $\blacksquare$
6.2 #9
4951 students suffice, as $\left\lceil \frac{4951}{50}\right\rceil = 100$.
(4950 students don’t suffice, as there could be 99 from each state.)
6.2 #16
5 numbers suffice. Proof: Regard the subsets $\{1,15\}$, $\{3,13\}$, $\{5,11\}$, $\{7,9\}$ as pigeonholes. If we choose 5 elements, some two from the same pigeonhole are chosen, and add up to 16. $\blacksquare$
(4 numbers don’t suffice, as the example of $\{1,3,5,7\}$ demonstrates.)
6.2 #44
Regard the subsets $\{1000,1001\},\{1002,1003\},\cdots,\{1098,1099\}$ as pigeonholes. There are 50 such subsets, so, with 51 houses, some two are in the same pigeonhole; their addresses are consecutive integers. $\blacksquare$