Mathematical Induction - Complete Induction

Another variant, called complete induction (or strong induction or course of values induction), says that in the second step we may assume not only that the statement holds for n = m but also that it is true for all n less than or equal to m.

Complete induction is most useful when several instances of the inductive hypothesis are required for each inductive step. For example, complete induction can be used to show that

where F_n is the nth Fibonacci number, φ = (1 + √5)/2 (the golden ratio) and ψ = (1 − √5)/2 are the roots of the polynomial x2 − x − 1. By using the fact that F_{n + 2} = F_{n + 1} + F_n for each n ∈ N, the identity above can be verified by direct calculation for F_{n + 2} if we assume that it already holds for both F_{n + 1} and F_n. To complete the proof, the identity must be verified in the two base cases n = 0 and n = 1.

Another proof by complete induction uses the hypothesis that the statement holds for all smaller n more thoroughly. Consider the statement that "every natural number greater than 1 is a product of prime numbers", and assume that for a given m > 1 it holds for all smaller n > 1. If m is prime then it is certainly a product of primes, and if not, then by definition it is a product: m = n₁ n₂, where neither of the factors is equal to 1; hence neither is equal to m, and so both are smaller than m. The induction hypothesis now applies to n₁ and n₂, so each one is a product of primes. Then m is a product of products of primes; i.e. a product of primes.

This generalization, complete induction, is equivalent to the ordinary mathematical induction described above. Suppose P(n) is the statement that we intend to prove by complete induction. Let Q(n) mean P(m) holds for all m such that 0 ≤ m ≤ n. Then Q(n) is true for all n if and only if P(n) is true for all n, and a proof of P(n) by complete induction is just the same thing as a proof of Q(n) by (ordinary) induction.