Re: Strong induction proofs

Technically, every proof by regular induction is also a proof by strong induction because in strong induction, you are *allowed* to use the hypotheses for all numbers up to n; you are not *required* to use any of them. Of course, for clarity we usually describe only the necessary tools used in a particular proof, so a proof that uses only the induction hypothesis for n is properly described as using regular induction.

Usually either regular or strong induction is more convenient. Proving the formula for the sum of an arithmetic progression is more convenient using regular induction, and proving that every natural number > 1 can be factorized into primes is more convenient using strong induction. Sometimes it is possible to give both proofs. For example, suppose we want to prove 1 + ... + (5n - 4) = n(5n - 3) / 2 from the hypotheses for all k < n. If n = 2k, then k < n since n ≥ 1. The left-hand side equals

1 + ... + (5k - 4) + (5k + 1) + ... + (5(2k) - 4) =

1 + ... + (5k - 4) + 5kČ + 1 + ... + (5k - 4) =

k(5k - 3) / 2 + 5kČ + k(5k - 3) / 2 =

10kČ - 3k

and the right-hand side also equals (2k)(5(2k) - 3) / 2 = 10kČ - 3k. The case when n = 2k + 1 should be considered similarly. However, this proof seems more complicated.

For another example where both regular and strong inductions are appropriate see this thread.