Finding the right hypothesis

In many cases, the induction follows immediately from the statement we want to prove, but often it helps to make the induction hypothesis stronger than the targeted statement. This might sound counter-intuitive, so let us try to absorb this idea via a few examples.

Example 15

The sum of the first $n$ (positive) odd numbers is a perfect square, i.e., $\sum_{i=1}^n (2i-1) = m^2$ for some integer $m$.

Proof:

You may want to use this statement itself as an induction hypothesis, but notice that you will run into difficulty (please try!). Instead, the right hypothesis to use is the following: $P(n): \sum_{i=1}^n (2i-1) = n^2$ When $n = 1$, this statement is obvious. Assume that $P(n_0)$ holds. To prove $P(n_0 + 1)$, notice that $\sum_{i=1}^{n_0+1} (2i − 1) = \sum_{i=1}^{n_0} (2i − 1) + (2n_0 + 1)$. The first term is $n_0^2$ by induction hypothesis, so we have $n_0^2 + 2n_0 + 1 = (n_0 + 1)^2$ which concludes the proof of $P(n_0 + 1)$.

Notice that in the above example, the induction hypothesis postulates an explicit form of the sum, while we are only aiming to prove that it is a perfect square. This is the part that apparently is counter-intuitive: Why would it be easier to prove a stronger statement? Before further discussions, let us look at another example.

Example 16

$\sum_{i=1}^n \frac{1}{i^2} \leq 2$.

Proof:

Students might be tempted to, again, try to use the statement itself as an induction hypothesis (and will realize that induction does not work). Instead, a stronger induction hypothesis would work: $P(n): \sum_{i=1}^n \frac{1}{i^2} \leq 2-1/n$ Notice that $P(1)$ is trivial. Now assume that $P(n_0)$ holds. To prove $P(n_0+1)$, we can write $\sum_{i=1}^{n_0+1} \frac{1}{i^2} = \sum_{i=1}^{n_0} \frac{1}{i^2} + \frac{1}{(n_0+1)^2}$. By induction hypothesis, the first term is at most $2- 1/n_0$, so we have $2- 1/n_0 + 1/(n_0+1)^2 = 2 - \frac{(n_0+1)^2-n_0}{n_0(n_0+1)^2}\leq 2- \frac{n_0^2 + n_0}{n_0(n_0+1)^2} = 2-1/(n_0+1)$

Again, the same phenomenon happens. We are trying to prove a stronger statement but it ends up being easier to prove. If we think carefully about what happened, it is not that surprising. A weaker hypothesis is too general and does not capture the true structure of the problem, while a stronger one does. Therefore, coming up with the right hypothesis requires a deeper understanding about the problem.

Exercise 5

Consider Fibonacci sequence $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$. Prove that every third Fibonacci number is even (e.g., $F_3 = 2$ and $F_6=8$ are even).