Next: The method of descent Up: Variant forms of expressing Previous: Variant forms of expressing

## Strong induction versus weak induction

Sometimes the definition given above for induction is called weak'' induction - as contrasted with strong induction'', defined as follows:

If is an integer, and is some property of integers, and
base case'':
is true and
induction step'':
whenever are all true, then is also true.
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:

is eventually constant. [That is, the sequence is defined: , . and you need to show that, for any positive integer , the sequence is eventually constant.]

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 .)

Next: The method of descent Up: Variant forms of expressing Previous: Variant forms of expressing
Zvezdelina Stankova-Frenkel 2001-11-18