Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers (positive integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.

Examples:

Mathematical induction can be used to prove that the following statement, which we will call P(n), holds for all natural numbers n.

P(n) gives a formula for the sum of the natural numbers less than or equal to number n. The proof that P(n) is true for each natural number n proceeds as follows.

Basis: Show that the statement holds for n = 0.
P(0) amounts to the statement:

In the left-hand side of the equation, the only term is 0, and so the left-hand side is simply equal to 0.
In the right-hand side of the equation, 0·(0 + 1)/2 = 0.
The two sides are equal, so the statement is true for n = 0. Thus it has been shown that P(0) holds.

Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:

Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:

Algebraically:

thereby showing that indeed P(k + 1) holds.

Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that P(n) holds for all natural n. Q.E.D.

Variants

In practice, proofs by induction are often structured differently, depending on the exact nature of the property to be proved.

Starting at some other number

If we want to prove a statement not for all natural numbers but only for all numbers greater than or equal to a certain number b then:

1. Showing that the statement holds when n = b.
2. Showing that if the statement holds for n = m ≥ b then the same statement also holds for n = m + 1.

This can be used, for example, to show that n² ≥ 3n for n ≥ 3. A more substantial example is a proof that

In this way we can prove that P(n) holds for all n ≥1, or even n ≥−5. This form of mathematical induction is actually a special case of the previous form because if the statement that we intend to prove is P(n) then proving it with these two rules is equivalent with proving P(n + b) for all natural numbers n with the first two steps.

Building on n = 2

In mathematics, many standard functions, including operations such as "+" and relations such as "=", are binary, meaning that they take two arguments. Often these functions possess properties that implicitly extend them to more than two arguments. For example, once addition a + b is defined and is known to satisfy the associativity property (a + b) + c = a + (b + c), then the ternary addition a + b + c makes sense, either as (a + b) + c or as a + (b + c). Similarly, many axioms and theorems in mathematics are stated only for the binary versions of mathematical operations and relations, and implicitly extend to higher-arity versions.

Suppose that we wish to prove a statement about an n-ary operation implicitly defined from a binary operation, using mathematical induction on n. Then it should come as no surprise that the n = 2 case carries special weight. Here are some examples.

Example: product rule for the derivative

In this example, the binary operation in question is multiplication (of functions). The usual product rule for the derivative taught in calculus states:

or in logarithmic derivative form

This can be generalized to a product of n functions. One has

or in logarithmic derivative form

In each of the n terms of the usual form, just one of the factors is a derivative; the others are not.

When this general fact is proved by mathematical induction, the n = 0 case is trivial, (since the empty product is 1, and the empty sum is 0). The n = 1 case is also trivial, And for each n ≥ 3, the case is easy to prove from the preceding n − 1 case. The real difficulty lies in the n = 2 case, which is why that is the one stated in the standard product rule.

Alternative way to look at this is to generalize (a monoid homomorphism) to .

Example: Pólya''s proof that there is no "horse of a different color"

In this example, the binary relation in question is an equivalence relation applied to horses, such that two horses are equivalent if they are the same color. The argument is essentially identical to the one above, but the crucial n = 1 case fails, causing the entire argument to be invalid.

In the middle of the 20th century, a commonplace colloquial locution to express the idea that something is unexpectedly different from the usual was "That''s a horse of a different color!". George Pólya posed the following exercise: Find the error in the following argument, which purports to prove by mathematical induction that all horses are of the same color:

• Basis: If there is only one horse, there is only one color.
• Induction step: Assume as induction hypothesis that within any set of n horses, there is only one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.

The basis case is trivial (as any horse is the same color as itself), and the inductive step is correct in all cases n > 2. However, the logic of the inductive step is incorrect for n = 2, because the statement that "the two sets overlap" is false (there are only two horses). Indeed, the n = 2 case is clearly the crux of the matter; if one could prove the n = 2 case directly, then all higher cases would follow from the inductive hypothesis.

Induction on more than one counter

It is sometimes desirable to prove a statement involving two natural numbers, n and m, by iterating the induction process. That is, one performs a basis step and an inductive step for n, and in each of those performs a basis step and an inductive step for m. See, for example, the proof of commutativity accompanying addition of natural numbers. More complicated arguments involving three or more counters are also possible.

Infinite descent

The method of infinite descent was one of Pierre de Fermat''s favorites. This method of proof can assume several slightly different forms. For example, it might begin by showing that if a statement is true for a natural number n it must also be true for some smaller natural number m (m < n). Using mathematical induction (implicitly) with the inductive hypothesis being that the statement is false for all natural numbers less than or equal to m, we can conclude that the statement cannot be true for any natural number n.

Although this particular form of infinite-descent proof is clearly a mathematical induction, whether one holds all proofs "by infinite descent" to be mathematical inductions depends on how one defines the term "proof by infinite descent." One might, for example, use the term to apply to proofs in which the well-ordering of the natural numbers is assumed, but not the principle of induction. Such, for example, is the usual proof that 2 has no rational square root (see Infinite descent).