1. Simple induction

Most of the ProofTechniques we've talked about so far are only really useful for proving a property of a single object (although we can sometimes use generalization to show that the same property is true of all objects in some set if we weren't too picky about which single object we started with). Mathematical induction (which mathematicians just call induction) is a powerful technique for showing that some property is true for many objects, where you can use the fact that it is true for small objects as part of the proof that it is true for large objects.

The basic framework for induction is as follows: given a sequence of statements P(0), P(1), P(2), we'll prove that P(0) is true (the base case), and then prove that for all k, P(k) => P(k+1) (the induction step). We then conclude that P(n) is in fact true for all n.

1.1. Why induction works

There are three ways to show that induction works, depending on where you got your natural numbers from.

Peano axioms: If you start with the PeanoAxioms, induction is one of them. Nothing more needs to be said.
Well-ordering of the naturals: A set is well-ordered if every subset has a smallest element. (An example of a set that is not well-ordered is the integers ℤ.) If you build the natural numbers using 0 = { } and x+1 = x ∪ {x}, it is possible to prove that the resulting set is well-ordered. Because it is well-ordered, if P(n) does not hold for all n, there is a smallest n for which P(n) is false. But then either this n = 0, contradicting the base case, or P(n-1) is true (because otherwise n would not be the smallest) and P(n) is false, contradicting the induction step.
Method of infinite descent: The original version, due to Fermat, goes like this: Suppose P(n) is false for some n > 0. Since P(n-1) => P(n) is logically equivalent to ¬P(n) => ¬P(n-1), we can conclude (using the induction step) ¬P(n-1). Repeat until you reach 0. The problem with this version is that the "repeat" step is in effect using an induction argument. The modern solution to this problem is to recast the argument to look like the well-ordering argument above, by assuming that n is the smallest n for which P(n) is false and asserting a contradiction once you prove ¬P(n-1). Historical note: Fermat may have used this technique to construct a false proof of his famous "Last Theorem" that aⁿ+bⁿ=cⁿ has no non-trivial integer solutions for n > 2.

1.2. Examples

DivisionAlgorithm.
Number of subsets of an n-element set is 2ⁿ.
1+3+5+7+...+(2n+1) = (n+1)².
2ⁿ > n² for n ≥ 5.

2. Strong induction

Sometimes when proving that the induction hypothesis holds for n+1, it helps to use the fact that it holds for all n' < n+1, not just for n. This sort of argument is called strong induction.

2.1. Example

Every n > 1 can be factored into a product of one or more prime numbers. Proof: By induction on n. The base case is n = 2, which factors as 2 = 2 (one prime factor). For n > 2, either (a) n is prime itself, in which case n = n is a prime factorization; or (b) n is not prime, in which case n = ab for some a and b. Since a and b are both less than n, by the induction hypothesis we have a = p₁p₂...p_k for some sequence of one or more primes and similarly b = p'₁p'₂...p'_k'. Then n = p₁p₂...p_kp'₁p'₂...p'_k' is a prime factorization of n.

3. Structural induction

See separate page StructuralInduction.

CategoryMathNotes