Prove that for all positive integer
Notice that the LHS of the above inequality increases as increases but the RHS remains constant. So induction doesn't immediately work here. To prove this inequality, we make a minor change on the expression as follows:
The goal is to determine a positive constant that will allow us to prove the inequality by induction. If this inequality is true, we can conclude that the original inequality is also true!
First, let's determine what should be. The induction step is:
Applying the induction hypothesis, we obtain
Expanding and simplifying, we need that
Now, this is clearly satisfied for .
It now remains to find a base case to make the strengthened statement true. For , we obtain
Thus, we will begin our induction on the strengthened statement and a base case of . We will deal with separately, since they do not satisfy the strengthened statement.
We didn't need to focus on a constant . We could make it a function and attempted to find a better shape. Of course, this additional specification leads to more complication, and it could no longer be so easy to find a suitable function.
In such problems where we "over-compensate," the strengthened induction hypothesis might not be true for some initial cases. We simply treat them as part of our base cases.