Mathematical Induction

In one sentence

Let $P (n)$ be a statement about a positive integer $n$ . If

Base case: $P (n_{0})$ holds;
Inductive step: whenever $P (k)$ holds (with $k \geq n_{0}$ ), $P (k + 1)$ follows,

then $P (n)$ holds for every $n \geq n_{0}$ . It is like a row of dominoes: the first one falls, each one knocks over the next, so they all fall.

“I checked lots of cases” is not enough. In the figure above, $n^{2} + n + 41$ is prime for every $n$ from $1$ to $39$ , but at $40$ it equals $4 1^{2}$ .

Example: 1 + 3 + 5 + … + (2n − 1) = n²

Step 1 / 4

Base case
$n = 1$ : the left side is $1$ and the right side is $1^{2} = 1$ . True, so the first domino can be pushed over.

$1 = 1^{2}$
Induction hypothesis
Inductive step
They all fall

Predict first

Take the statement $2^{n} > n^{2}$ . From which $n_{0}$ on does it hold for every $n \geq n_{0}$ (give the smallest $n_{0}$ )?

Choose an answer first; then you can see the result.

Stop 1 · Strong induction (Vol. 5)

When the recurrence involves the previous two terms, assuming $P (k)$ alone is not enough: assume both $P (k)$ and $P (k - 1)$ , and check two base cases as well.

Example: a₁ = 1, a₂ = 3, aₙ₊₂ = 3aₙ₊₁ − 2aₙ. Prove that aₙ = 2ⁿ − 1

Step 1 / 4

Base case: two dominoes
$a_{1} = 1 = 2^{1} - 1$ , $a_{2} = 3 = 2^{2} - 1$ .

$a_{1} = 2^{1} - 1, a_{2} = 2^{2} - 1$
Assume two terms
Get the next term
Conclusion

Stop 2 · Choosing the right step size (Vol. 5)

You do not have to go from $k$ to $k + 1$ . If going from $k$ to $k + 3$ is more natural, take steps of $3$ ; just get $3$ starting points ready.

Example: any postage of n ≥ 8 cents can be made with 3-cent and 5-cent stamps

Step 1 / 4

Choose step size 3
If you can make $k$ cents, one more $3$ -cent stamp makes $k + 3$ cents. Each step jumps by $3$ .

$P (k) \Rightarrow P (k + 3)$
Three base cases
Three chains
Why start at 8

Stop 3 · Strengthening the statement (Vol. 5)

Sometimes the original statement is “too weak”: the induction hypothesis does not give enough to push on. Proving a stronger statement goes through more easily.

One problem, several solutions

Prove that for every positive integer $n$ , $1 + \frac{1}{2 ^{2}} + \frac{1}{3 ^{2}} + \dots + \frac{1}{n ^{2}} < 2$ .

Plain induction: stuck

Suppose $S_{k} < 2$ . Then $S_{k + 1} = S_{k} + \frac{1}{( k + 1 ) ^{2}} < 2 + \frac{1}{( k + 1 ) ^{2}}$ .

The right side is bigger than $2$ , so nothing follows. The trouble is that “ $< 2$ ” does not say how far below $2$ we are.

CostThe hypothesis only says “less than 2”; after one more term, you know nothing.

Strengthen to S_n ≤ 2 − 1/n

$n = 1$ : $1 \leq 2 - 1$ , true. Suppose $S_{k} \leq 2 - \frac{1}{k}$ . Then

$S_{k + 1} \leq 2 - \frac{1}{k} + \frac{1}{( k + 1 ) ^{2}} \leq 2 - \frac{1}{k} + \frac{1}{k ( k + 1 )} = 2 - \frac{1}{k + 1} .$

This uses $\frac{1}{( k + 1 ) ^{2}} < \frac{1}{k ( k + 1 )} = \frac{1}{k} - \frac{1}{k + 1}$ . Hence $S_{n} \leq 2 - \frac{1}{n} < 2$ .

CostA stronger claim, but also a stronger hypothesis: just enough.

Stop 4 · Proving the mean inequality (Vol. 6)

Cauchy's forward–backward induction: first leap along $2, 4, 8, \dots$ , then step back one at a time to fill in the $n$ in between.

Example: prove that the arithmetic mean of n positive numbers is ≥ their geometric mean

Step 1 / 4

Base case n = 2
$\frac{a + b}{2} \geq ab$ is equivalent to $(a - b)^{2} \geq 0$ .

$\frac{a + b}{2} \geq ab$
Forward: n → 2n
Backward: n → n − 1
Everything is covered

Practice

Exercise 1Basic

With $3$ -cent and $5$ -cent stamps (as many as you like), what is the largest postage, in cents, that cannot be made?

Exercise 2Basic

What is the smallest positive integer $N$ such that $n^{2} < 2^{n}$ for every $n \geq N$ ?

Exercise 3Advanced

Prove that for every positive integer $n$ , $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} < 2 n$ .

Exercise 4Challenge

Given $a_{1} = 1$ and $a_{n + 1} = a_{n} + \frac{1}{a _{n}}$ , prove that $a_{n} \geq 2 n - 1$ for every positive integer $n$ .

In one sentence

Example: 1 + 3 + 5 + … + (2n − 1) = n²

Stop 1 · Strong induction (Vol. 5)

Example: a₁ = 1, a₂ = 3, aₙ₊₂ = 3aₙ₊₁ − 2aₙ. Prove that aₙ = 2ⁿ − 1

Stop 2 · Choosing the right step size (Vol. 5)

Example: any postage of n ≥ 8 cents can be made with 3-cent and 5-cent stamps

Stop 3 · Strengthening the statement (Vol. 5)

Plain induction: stuck

Strengthen to S_n ≤ 2 − 1/n

Stop 4 · Proving the mean inequality (Vol. 6)

Example: prove that the arithmetic mean of n positive numbers is ≥ their geometric mean

Practice

Mistake Museum · Exhibits from this stop

Proving the step but never checking the base

Step size 3, but only one base case

Stops on this line