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 Fn 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 Fn + 2 = Fn + 1 + Fn for each n ∈ N, the identity above can be verified by direct calculation for Fn + 2 if we assume that it already holds for both Fn + 1 and Fn. 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 = n1 n2, 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 n1 and n2, 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.
Read more about this topic: Mathematical Induction
Famous quotes containing the words complete and/or induction:
“Thus when I come to shape here at this table between my hands the story of my life and set it before you as a complete thing, I have to recall things gone far, gone deep, sunk into this life or that and become part of it; dreams, too, things surrounding me, and the inmates, those old half-articulate ghosts who keep up their hauntings by day and night ... shadows of people one might have been; unborn selves.”
—Virginia Woolf (1882–1941)
“They relieve and recommend each other, and the sanity of society is a balance of a thousand insanities. She punishes abstractionists, and will only forgive an induction which is rare and casual.”
—Ralph Waldo Emerson (1803–1882)