Redirected from Proof by induction
The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps:
To understand why the two steps are in fact sufficient, it is helpful to think of the domino effect: if you have a long row of dominos standing on end and you can be sure that
Example Suppose we wish to prove the statement:
for all natural numbers n. This is a simple formula for the sum of the natural numbers up to the number n. The proof that the statement is true for all natural numbers n proceeds as follows.
Now we have to show that if the statement holds when n = m, then it also holds when n = m + 1. This can be done as follows.
Assume the statement is true for n = m, i.e.,
Adding m + 1 to both sides gives
By algebraic manipulation we have
Thus we have
This is that statement for n = m + 1. Note that it has not been proved as true: we made the assumption that P( m ) is true, and from that assumption we derived P( m + 1 ). Symbolically, we have shown that:
However, by induction, we may now conclude that the statement P(n) holds for all natural numbers n:
This type of proof can be generalized in several ways. For instance, 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 the following steps are sufficient:
Another generalization allows that in the second step we not only assume that the statement holds for n = m but also for all n smaller than or equal to m. This leads to the following two steps:
This can be used, for example, to show that fib(n) = [Φn - (-1/Φ)n ] / 51/2 where fib(n) is the nth Fibonacci number and Φ = (1 + 51/2) / 2 (the socalled Golden mean). Since fib(m + 1) = fib(m) + fib(m - 1) it is straightforward to prove that the statement holds for m + 1 if we can assume that it already holds for both m and m - 1. Also for this generalization it holds that it is in fact just a special case of the first form; let P(n) be the statement that we intend to prove then proving it with these rules is equivalent with proving the statement ' P(m) for all m <= n ' for all natural numbers n with the first two steps.
The last two steps can be reformulated as one step:
This is in fact the most general form of mathematical induction and it can be shown that it is not only valid for statements about natural numbers, but for statements about elements of any well-founded set, that is, a set with a partial order that contains no infinite descending chains (where < is defined such that a < b iff a <= b and a ≠ b).
This form of induction, when applied to ordinals (which form a well-ordered and hence well-founded class), is called transfinite induction. It is an important proof technique in set theory, topology and other fields.
Proofs by transfinite induction typically need to distinguish three cases:
Proof of method Mathematical induction is taught in schools, and most students learn it by rote without fully understanding how it works. It is possible to base a proof of mathematical induction on other mathematical principles.
Related methods An induction variant is used in computer science to prove that expressions which can be evaluated are equivalent, and this is known as structural induction.
Alternative Formulations An alternative formulation of the principle of mathematical induction is the Well-Ordering Principle, which states that any nonempty set of natural numbers must have a smallest element. This principle is equivalent to mathematical induction, as follows:
Suppose that the well-ordering principle is true, and that the conditions of the proof by induction are true, namely, that for some property P, we know that P(0) is true, and that if P(n) is true for any natural number n, then P(n+1) is also true. We wish to prove that P(n) is true for all natural numbers n. Let S be the set of natural numbers for which P is not true. Let us suppose that S has a smallest element, say m. m cannot be 0, because P(0) is true by hypothesis. So m-1 is a natural number, and in particular m-1 is not an element of S, because m is the smallest element of S. So P(m-1) is true, and by hypothesis P(m) is also true, and we have a contradiction. Thus we conclude that S has no smallest element, and so by the well-ordering principle, S must be empty. P(n) therefore holds for all natural numbers n.
Conversely, we can prove the well-ordering principle inductively. Let S be a set of natural numbers. We want to prove that either S has a smallest element or else that S is empty. Let P(n) be the statement that no element of S is smaller than n. P(0) is certainly true, since there is no natural number smaller than 0. Suppose that P(n) is true for some n. If P(n+1) were false, then S would have an element smaller than n+1, but it could not be smaller than n, because P(n) was true, and so S would have a minimal element, namely n, and we would be done. So P(n) implies P(n+1) for all n, or else S has a minimal element. But if P(n) implies P(n+1) for all n, then by induction we know that P(n) is true for all n, and therefore for all n, no element of S is smaller than n. But this can only be vacuously true, if S has no elements at all, since every natural number is smaller than some other natural number. Thus we are done.
An analogous proof holds for any well-ordered set; see transfinite induction.
See also three forms of mathematical induction.
Search Encyclopedia
|
Featured Article
|