Consider the statement:
- Prove that if the statement is true for an integer , then it is also true for .
- What is wrong with the claim that this proves that is true for all ?
- Make a change to turn this into a true statement and prove it for all positive integers.
Proof. Assume the statement is true for an integer . Then, adding to both sides of the formula we assume is true for the case ,
Thus, the statement is true for if it is true for
- Of course, the above is not a proof by induction, and does not show that the statement is true for all since we have not shown that it is true for any base case. We have shown that if it is true for some , then it is true for . To show that it is true for all , we must show that it is true for the case (or some other starting point). As one can calculate, it is not true for , or any other for that matter.
- In the case we have 1 on the left, and on the right. So, we make the following:
Proof. We have already shown it is true for since . Now assume it is true for some integer , then using the inductive hypothesis and adding to both sides we have
Thus, the inequality is true for all