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 $k$ is an integer, and $P$ is some property of integers, and

``base case'':

$P(k)$ is true and

``induction step'':

whenever $P(k),P(k+1),P(k+2),\ldots,P(n)$ are all true, then $P(n+1)$ is also true.

then $P(n)$ is true for all integers $n \geq k$.

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 $n \geq 1$, the sequence:

$$2, 2^2, 2^{(2^2)}, 2^{\left(2^{(2^2)}\right)}, \ldots \pmod n$$

is eventually constant. [That is, the sequence is defined: $a_1=2$, $a_{i+1} = 2^{a_i}$. and you need to show that, for any positive integer $n$, the sequence $a_1 \bmod n, \, a_2 \bmod n, \ldots$ is eventually constant.]

This problem actually requires, in addition to induction, a little bit of number theory. Just because $a \equiv b \pmod n$ doesn't mean $2^a \equiv 2^b \pmod n$. What must be true of $a$ and $b$ in order for $2^a$ to be congruent to $2^b$ mod $n$? (Hint: think of the Euler-Fermat theorem and $\phi(n)$.)