If is an integer, and is some property of integers, and
then is true for all integers .
The difference is in what you need to assume in the induction step. For ordinary induction--in the ladder metaphor--you simply go from the rung you are on up to the next one. For strong induction, you need to know that all the rungs below the rung you are on are solid in order to step up. As a practical matter, both have the same logical strength when you apply them - since as you climb up the ladder from the bottom rung, you sweep through all the intermediate rungs anyway. However, sometimes strong induction makes the proof of the induction step easier.
7 The proof that every integer greater than 1 may be written as the product of prime numbers is usually written with this form of induction.
8 (1991 USAMO) Show that for any fixed integer , the sequence:
This problem actually requires, in addition to induction, a little bit of number theory. Just because doesn't mean . What must be true of and in order for to be congruent to mod ? (Hint: think of the Euler-Fermat theorem and .)