In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption.
Why then, in some other cases, is it necessary to provide several base cases instead of just assuming that P(k) is true in each of those base cases?
For instance, the claim, every amount of postage that is at least 12 cents can be made from 4-cent and 5-cent stamps. Why is it necessary to show the base cases up to 16 cents rather than just starting at P(k=16) and saying suppose 12 <= k is all true?
Best Answer
Strong induction is often used where there is a recurrence relation, i.e. $a_{n} = a_{n-1}-a_{n-2}$. In this situation, since 2 different steps are needed to work with the given formula, you need to have at least 2 base cases to avoid any holes in your proof. Proving it works for $n=1$ doesn't help since if you try to use the relation for $n=2$ you get an undefined $a_{-1}$ term.