Induction: infinitely many dominoes
Tonight's idea
How do you prove something for every whole number \(n = 1, 2, 3, \ldots\)? Picture an infinite row of dominoes. If the first one falls, and whenever one falls the next falls too, then they all fall. That is mathematical induction.
Write \(P(n)\) for "the statement is true for \(n\)". To prove \(P(n)\) for all \(n \ge 1\): Base case. Show \(P(1)\). Inductive step. Assume \(P(k)\) for some \(k \ge 1\) (the inductive hypothesis) and deduce \(P(k+1)\).
Example: \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\). Base case, \(n = 1\): both sides are 1. Step: assume \(1 + \cdots + k = k(k+1)/2\) and add \(k+1\):
\[ \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}, \]which is the formula with \(n = k+1\). The dominoes fall.
Induction never finds the formula; someone has to guess it first. It turns a pattern you have spotted into a theorem.
Watch one: \(2^n > n^2\) for all \(n \ge 5\)
Small cases: \(2^3 = 8 \lt 9\), \(2^4 = 16 = 16\), \(2^5 = 32 > 25\). So the first domino is \(n = 5\); induction is happy to start anywhere.
Base case. \(32 > 25\). Step. Assume \(2^k > k^2\) with \(k \ge 5\). Then \(2^{k+1} = 2 \cdot 2^k > 2k^2\), and we want \((k+1)^2 = k^2 + 2k + 1\). It is enough that \(2k^2 \ge k^2 + 2k + 1\), i.e. \((k-1)^2 \ge 2\), which is true for \(k \ge 5\). So \(2^{k+1} > 2k^2 \ge (k+1)^2\).
The move to remember: use the hypothesis to get most of the way, then a little algebra closes the gap.
Your turn
- Prove \(1 + 3 + 5 + \cdots + (2n-1) = n^2\). Write out the base case and the inductive step.
- Tower of Hanoi. The fewest moves for \(n\) discs satisfies \(T_1 = 1\) and \(T_n = 2T_{n-1} + 1\). Prove by induction that \(T_n = 2^n - 1\). Play it at mathdetours.com/demos/hanoi.html.
- Prove that \(n^3 - n\) is divisible by 6 for every \(n \ge 1\). (Hint: expand \((k+1)^3 - (k+1)\) and separate out \(k^3 - k\).)
- Find the flaw. "All horses are the same colour. Base: one horse is the same colour as itself. Step: in any \(k+1\) horses, the first \(k\) share a colour, the last \(k\) share a colour, and the groups overlap, so all \(k+1\) share a colour." Exactly which step from \(k\) to \(k+1\) fails, and why?
Stretch: strong induction and stamps
Strong induction assumes \(P(1), \ldots, P(k)\) all hold when proving \(P(k+1)\). Prove that every postage from 12 cents upward can be made with 4-cent and 5-cent stamps: check 12, 13, 14, 15 by hand, then show that if \(k\) works, so does \(k + 4\). Why is 11 cents impossible?
Answers
- Base: \(1 = 1^2\). Step: assume \(1 + \cdots + (2k-1) = k^2\); add \(2k+1\): \(k^2 + 2k + 1 = (k+1)^2\).
- Base: \(T_1 = 1 = 2^1 - 1\). Step: assume \(T_k = 2^k - 1\). Then \(T_{k+1} = 2T_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1\).
- Base: \(1 - 1 = 0\). Step: \((k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)\). The first bracket is a multiple of 6 by hypothesis; \(k(k+1)\) is a product of consecutive numbers, so even, so \(3k(k+1)\) is a multiple of 6.
- The step from \(k = 1\) to \(k = 2\) fails: with two horses, "the first 1" and "the last 1" do not overlap, so nothing links their colours. The step works from 2 onward, but the first domino never pushes the second, so none fall.
Stretch. \(12 = 4+4+4\), \(13 = 4+4+5\), \(14 = 4+5+5\), \(15 = 5+5+5\). If \(k \ge 12\) can be made, add a 4-cent stamp for \(k+4\). Every \(n \ge 12\) is one of 12 to 15 plus a multiple of 4, so these cover everything. For 11: no 5s gives multiples of 4; one 5 leaves 6; two 5s leave 1. None works.