Changing the Statement

In one sentence

In mathematical induction, the induction hypothesis is all the capital you have. The stronger the conclusion you set out to prove, the stronger the hypothesis. So when a direct proof gets stuck, deliberately make the statement stronger:

strengthen the statement: write the “room” into the conclusion, e.g. change $\leq 2$ into $\leq 2 - \frac{1}{n}$ ;
use an auxiliary statement: first prove a property that carries over from step to step, and get the original statement as a corollary;
generalize the statement: put the special case inside a more general statement that is easier to induct on.

It sounds like asking for trouble — you have more to prove, and yet it gets easier.

Example: 1 + 1/4 + 1/9 + … + 1/n² < 2

Step 1 / 5

Straight induction
Assume $S_{n} \leq 2$ . Then $S_{n + 1} = S_{n} + \frac{1}{( n + 1 ) ^{2}} \leq 2 + \frac{1}{( n + 1 ) ^{2}}$ . The bound got bigger, so $S_{n + 1} \leq 2$ does not follow. Every step in the table is ✗ — not because the statement is wrong, but because the hypothesis is too weak.

$S_{n + 1} \leq 2 + \frac{1}{( n + 1 ) ^{2}} does not give S_{n + 1} \leq 2$
Leave some room
How much room a step needs
How much the base allows
Exactly a = 1

Predict first

To prove $S_{n} < 2$ by induction, which strengthened statement lets the induction go through (base case and every step)?

S_{n} \leq 2 - \frac{1}{2 n}

S_{n} \leq 2 - \frac{1}{n}

S_{n} \leq 2 - \frac{2}{n}

S_{n} \leq \frac{3}{2}

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

Stop 1 · Sequences: an auxiliary statement

Example A sequence has $a_{1} = a_{2} = 1$ and $a_{n + 1} = \frac{a _{n}^{2} + 2}{a _{n - 1}}$ ( $n \geq 2$ ). Prove that every term is an integer.

Straight induction: if $a_{1}, \dots, a_{n}$ are integers, $a_{n + 1}$ is one integer divided by another, which is not necessarily an integer. The hypothesis lacks information like “ $a_{n - 1}$ divides $a_{n}^{2} + 2$ ”. Compute a few terms: $1, 1, 3, 11, 41, 153, \dots$ — could it be that $a_{n + 1} = 4 a_{n} - a_{n - 1}$ ?

Auxiliary statement: it satisfies a linear recurrence

Step 1 / 4

Write two neighboring equations
By definition $a_{n + 1} a_{n - 1} = a_{n}^{2} + 2$ ; replacing $n$ by $n + 1$ gives $a_{n + 2} a_{n} = a_{n + 1}^{2} + 2$ .

$a_{n + 2} a_{n} - a_{n + 1} a_{n - 1} = a_{n + 1}^{2} - a_{n}^{2}$
Regroup
A ratio that never changes
The original statement is a corollary

Stop 2 · Combinatorics: generalize the statement

Example Remove a corner cell from a $2^{n} \times 2^{n}$ board. Prove that the rest can be tiled by L-trominoes (a $2 \times 2$ square minus one cell).

Straight induction: cut the board into four $2^{n - 1} \times 2^{n - 1}$ quarters. The hypothesis handles the quarter with the missing corner — but the other three quarters are complete, with no cell missing, and the hypothesis says nothing about them.

Generalize: remove any one cell

Step 1 / 4

Make the statement more general
Prove: a $2^{n} \times 2^{n}$ board with any one cell removed can be tiled by L-trominoes. The corner cell is just a special case.

$P (n) : remove any one cell, and the rest can be tiled$
Base case
Cut into quarters
Place one in the center

Proving only “corner removed”, the hypothesis is too narrow; generalize to “any cell removed” and the hypothesis is wide enough for the induction to turn. It is the same idea as in the first example.

Practice

Exercise 1Basic

Find $\frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \dots + \frac{1}{9 \times 10}$ .

Exercise 2Basic

Compute $S_{4} = 1 + \frac{1}{2 ^{2}} + \frac{1}{3 ^{2}} + \frac{1}{4 ^{2}}$ (as a fraction in lowest terms) and check that it really is at most the bound $2 - \frac{1}{4}$ from the strengthened statement.

Exercise 3Advanced

For the sequence of Stop 1, find $a_{6}$ .

Exercise 4Challenge

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

In one sentence

Example: 1 + 1/4 + 1/9 + … + 1/n² < 2

Stop 1 · Sequences: an auxiliary statement

Auxiliary statement: it satisfies a linear recurrence

Stop 2 · Combinatorics: generalize the statement

Generalize: remove any one cell

Practice

Mistake Museum · Exhibits from this stop

“The added term is tiny”, so it cannot go over

Strengthening too much