We illustrate strong induction in the following:

Example 4. Let a, b, c, r, s, and t be fixed integers. Let L₀, L₁,... be the Lucas sequence. Prove that

is true for n = 0, 1, 2, ... if it is true for n = 0 and n = 1.

Proof: We use strong induction. It is given that (A) is true for n = 0 and n = 1. Hence, it remains to assume that  and that (A) is true for n = 0, 1, 2, ..., k, and to use these assumptions to prove that (A) holds for n = k + 1.

We therefore assume that

and that there are at least two equations in this list. Adding corresponding sides of the last two of these equations and combining like terms, we obtain

Using the relation L_n+1 + L_n = L_n+2 for the Lucas numbers, this becomes

which is (A) when n = k + 1. This completes the proof.
 

Saturday, April 11, 1998