Induction with Base Case Not 1
Sometimes in proving induction, the statements does not always hold true at , but starts to be true at some value instead, let's say .
Let's think about this as a domino again. If the one doesn't fall, take the as a starting point. Next, we have to prove that for every positive integer , if the falls, the also falls. If we can prove it, we can conclude that always holds true for every positive integer .
Generalized induction:
Let , and we are given the following:
- is true.
- and , if is true, is always true.
Then we can say that is true for all .
Now we see that if we want to prove to be true, we need to prove those 2 statements, which is similar to proving by normal induction.
Now let's try an example.
Prove that for every positive integer .
Let be the statement "".
We see that the statement is not true for so we start with instead. Clearly, . Now we try to prove the induction step.
Let be true for , then we need to prove to be true.
Since is true by assumption, we get is true. Again, since we get Hence, we have
Therefore, which means is true for every if is true.
Thus by induction, we get is true for every .
Everything is the same as proving induction, just the base case is not equal to 1. Let's try the exercise!
Prove that for all positive integer .
Prove that for all positive integer .
Challenge for advanced: Prove that for all positive integers .
Hint: Claim that and try to make it as binomial expansion.