Strong Induction & Well-Ordering

Let $P(n)$: "you can run $n$ miles." We prove $P(n)$ for all $n\ge 1$.

Basis step. We are told we can run 1 mile and 2 miles, so $P(1)$ and $P(2)$ are true. Two base cases are needed because the step reaches back 2.

Inductive step. Let $k\ge 2$ and assume $P(j)$ is true for all $1\le j\le k$ (strong IH). We show $P(k+1)$.

Since $k\ge 2$, we have $1\le k-1\le k$, so by the IH you can run $k-1$ miles. Because you can always run two more miles, you can run $(k-1)+2=k+1$ miles. So $P(k+1)$ is true.

Conclusion. By strong induction you can run $n$ miles for every positive integer $n$. ∎

a) $8=3+5$, $9=3+3+3$, $10=5+5$. So $P(8),P(9),P(10)$ are true.

b) For an arbitrary integer $k\ge 10$: $P(j)$ is true for all integers $j$ with $8\le j\le k$. That is, every amount from 8 up to $k$ cents can be formed.

c) Assuming the IH, show $P(k+1)$: that $k+1$ cents can be formed with 3¢ and 5¢ stamps.

d) Since $k\ge 10$, $k-2\ge 8$, so $8\le k-2\le k$ and the IH says $P(k-2)$ is true: we can form $k-2$ cents. Add one 3-cent stamp to get $(k-2)+3=k+1$ cents. So $P(k+1)$ holds.

e) We have shown the basis cases $P(8),P(9),P(10)$, and that $[P(8)\wedge \cdots \wedge P(k)]\to P(k+1)$ for every $k\ge 10$. By the principle of strong induction, $P(n)$ is true for every integer $n\ge 8$.

a) Amounts are $4a+11b$ with $a,b\ge 0$:

• $b=0$: 4, 8, 12, 16, 20, 24, 28, …
• $b=1$: 11, 15, 19, 23, 27, …
• $b=2$: 22, 26, 30, …

Check 29: $29-11=18$ and $29-22=7$ are not multiples of 4, and 29 itself isn't, so 29 is impossible. Then $30=22+8$, $31=11+20$, $32=4\cdot 8$, $33=3\cdot 11$: four in a row. Since the smallest stamp is 4, everything from 30 up works.

Possible amounts: 4, 8, 11, 12, 15, 16, 19, 20, 22, 23, 24, 26, 27, 28, and all $n\ge 30$.

b) Ordinary induction. Let $P(n)$: "$n$ cents can be formed with 4¢ and 11¢ stamps." Prove for $n\ge 30$.

Basis: $30=11+11+4+4$.

Inductive step: Assume $P(k)$ for some $k\ge 30$ (IH: $k$ cents can be formed). Show $P(k+1)$:

• If the $k$-cent arrangement uses at least one 11¢ stamp, replace one 11¢ stamp with three 4¢ stamps: $-11+12=+1$. Now we have $k+1$.
• If it uses no 11¢ stamps, then it is all 4¢ stamps, and since $k\ge 30$ there are at least $8$ of them ($k\ge 32$ in fact). Replace eight 4¢ stamps (32¢) with three 11¢ stamps (33¢): $+1$. Now we have $k+1$.

Either way $P(k+1)$ holds. ∎

c) Strong induction. Basis: $30=11+11+4+4$, $31=11+4\cdot 5$, $32=4\cdot 8$, $33=11\cdot 3$. That's four cases because we step back by 4.

Inductive step: Let $k\ge 33$ and assume $P(j)$ for all $30\le j\le k$. Since $k\ge 33$, $30\le k-3\le k$, so $k-3$ cents can be formed. Add a 4¢ stamp: $k+1$ cents. ∎

Difference: In (b) the IH is only that $P(k)$ is true. In (c) the IH is that $P(j)$ is true for every $j$ from 30 through $k$, which lets us jump back to $k-3$.

Which amounts? 2, 4, 5, 6, 7 (=2+5), 8, 9 (=4+5), … Amounts 1 and 3 are impossible (3 isn't 2 or 5, and $3-2=1$ is impossible). From 4 on, 4 and 5 are two consecutive amounts and the smallest bill is 2, so every amount $\ge 4$ works. Answer: all $n\ge 1$ except $n=1$ and $n=3$.

Proof (for $n\ge 4$; $n=2$ is just one 2-dollar bill). Let $P(n)$: "$n$ dollars can be formed using 2- and 5-dollar bills."

Basis: $4=2+2$ and $5=5$. We step back by 2, so we need two base cases.

Inductive step: Let $k\ge 5$ and assume $P(j)$ for all $4\le j\le k$. Since $k\ge 5$, $4\le k-1\le k$, so $k-1$ dollars can be formed. Add a 2-dollar bill to get $k+1$ dollars. So $P(k+1)$ holds.

By strong induction, $P(n)$ is true for all $n\ge 4$. Together with $n=2$, every amount except 1 and 3 dollars can be formed. ∎

Let $P(n)$: "$n$ cents of postage can be formed using only 3¢ and 7¢ stamps." We prove $P(n)$ for all $n\ge 12$.

Basis step (3 cases, since we will step back by 3):

• $12=3+3+3+3$
• $13=3+3+7$
• $14=7+7$

Inductive step. Let $k\ge 14$. Assume (strong IH) $P(j)$ is true for all integers $j$ with $12\le j\le k$. Since $k\ge 14$, we have $12\le k-2\le k$, so by the IH we can form $k-2$ cents. Adding one 3¢ stamp forms $(k-2)+3=k+1$ cents. So $P(k+1)$ is true.

Conclusion. By strong induction, every amount of postage $\ge 12$ cents can be formed. ∎

(Side note: 11¢ is impossible, since 11, 8, 5, 2 are not multiples of 3 and $11-7=4$ isn't either. So 12 is the best starting point.)

Let $P(n)$: $a_n<2^n$.

Basis step. The recurrence looks back 3 terms, so check three cases: $a_1=1<2$, $a_2=2<4$, $a_3=3<8$.

Inductive step. Let $k\ge 3$ and assume $a_j<2^j$ for all $1\le j\le k$. Then since $k+1\ge 4$,
$$a_{k+1}=a_k+a_{k-1}+a_{k-2}<2^k+2^{k-1}+2^{k-2}=2^{k-2}(4+2+1)=7\cdot 2^{k-2}<8\cdot 2^{k-2}=2^{k+1}.$$
(We used the IH on $k$, $k-1$, $k-2$, all of which are $\ge 1$ because $k\ge 3$.)

By strong induction, $a_n<2^n$ for all $n\ge 1$. ∎

• a) Yes. This is exactly the well-ordering property.
• b) No. $\mathbb{Z}$ itself (or e.g. the negative integers) has no least element.
• c) Yes. Shift by 100: $x\mapsto x+100$ maps this set onto $\mathbb{N}$ preserving order, so every nonempty subset has a least element.
• d) No. The subset $\{1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots \}$ has no least element (and neither does ${\mathbb{Q}}^{+}$ itself).
• e) Yes. It's a subset of $\mathbb{N}$, and any nonempty subset of it is a nonempty subset of $\mathbb{N}$.

Let $P(n)$: "any rectangular bar with $n$ squares needs exactly $n-1$ breaks."

Basis. $n=1$: a single square needs $0=1-1$ breaks.

Inductive step. Let $k\ge 1$ and assume $P(j)$ for all $1\le j\le k$. Take a bar with $k+1$ squares. The first break splits it into two rectangles with $j$ and $k+1-j$ squares, where $1\le j\le k$. Both pieces have between 1 and $k$ squares, so by the IH they need $j-1$ and $k-j$ more breaks. Total:
$$1+(j-1)+(k-j)=k=(k+1)-1.$$
So $P(k+1)$ holds. By strong induction, $P(n)$ holds for all $n\ge 1$. ∎

This needs strong induction: the pieces can be any size, not just $k$.