Misplaced Pages

Revision as of 21:38, 5 March 2006

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. A somewhat more general form of argument used in mathematical logic and computer science replaces the natural numbers by other well--founded structures, such as trees; this is known as structural induction. It is important to note that mathematical induction is a rigorous method of proof: there are no degrees of uncertainty. In fact, mathematical induction is a type of deductive reasoning. This is in contrast with inductive reasoning, which is sometimes argued as being non-rigorous. (See Problem of induction for more.)

The first known proof by mathematical induction appears in Francesco Maurolico's Arithmeticorum libri fuo (1575). Maurolico proved that the sum of the first n odd integers is n.

The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps:

1. The basis: showing that the statement holds when n = 1.
2. The inductive step: showing that if the statement holds for n = m, then the same statement also holds for n = m + 1. (The proposition following the word "if" is called the induction hypothesis. Do not call step 2 as a whole the induction hypothesis.)

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if you have a long row of dominoes standing on end and you can be sure that:

1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.

then you can conclude that all dominoes will fall.

Example

Suppose we wish to prove the statement:

${\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}$

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.

Proof

Check if it is true for n = 1. Clearly, the sum of the first natural numbers is 1, and 1(1 + 1) / 2 = 1. So the statement is true for n = 1. We could define the statement as P(n), and thus we have that P(1) holds.

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.,

${\displaystyle 1+2+\cdots +m={\frac {m(m+1)}{2}}}$

Adding m + 1 (which is clearly the left-hand side's next term) to both sides gives

${\displaystyle 1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)}$

By algebraic manipulation we have

${\displaystyle ={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}}$

Thus we have

${\displaystyle 1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}}$

This is the statement for n = m + 1. It has not been proven 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:

${\displaystyle P(m)\Rightarrow P(m+1)}$

However, by induction:

1. We have P(1), i.e. the equation holds if n has the value of 1.
2. Hence, P(m) holds for m = 1, but P(m+1) has been established. Thus, P(2) follows.
3. With P(2), P(3) follows; and with P(3), P(4) may be asserted.
4. Et cetera.
5. We may conclude that P(n) holds for any natural number n.

Q.E.D.

Generalizations

Start at b

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:

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 > 2n for n ≥ 3. In this way we can prove also claims P(n) that hold for all n ≥0, 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.

Such a strategy can also be useful to prove a statement for all n. Possibly the case n = 1 is vacuously true; the step that goes from case n to case n + 1 is trivial if n > 1 and impossible if n = 1; the substantial part of the proof is the case n = 2, and the case n = 2 is relied on in the trivial induction step.

Assume true for all lesser values

Another generalization, called complete induction (or strong induction), allows that in the second step we assume not only that the statement holds for n = m but also that it is true for n smaller than or equal to m.

Perhaps surprisingly, in this form of induction, it is not necessary to prove that the proposition is true in the first case! That is because it is vacuously true that the proposition holds in all cases before the first case, simply because there are no cases before the first case. Note that the proof then of the step needs to be able to work with an empty antecedent; the first proof above is not of this kind (but can be converted).

This can be used, for example, to show that

${\displaystyle \operatorname {fib} (n)={\frac {\varphi ^{n}-(-1/\varphi )^{n}}{\sqrt {5}}}}$

where fib(n) is the n Fibonacci number and Φ = (1 + √5)/2 (the so-called golden ratio). Given that fib(m + 1) = fib(m) + fib(m − 1), it can be proven that that the statement holds for m + 1 if we can assume that it already holds for both m and m − 1. (Hence the proof of this identity requires a double basis - it requires initial demonstration that the identity is true for both n = 0 and n = 1).

This generalization is just a special case of the first form:

1. let P(n) be the statement that we intend to prove,
2. then proving it with these rules is equivalent to proving the statement "P(m) for all m ≤ n" for all natural numbers n with the first two steps.

Transfinite induction

The last two steps can be reformulated as one step:

1. Showing that if the statement holds for all n < m then the same statement also holds for n = m.

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 means that 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 distinguish three cases:

1. when m is a minimal element, i.e. there is no element smaller than m
2. when m has a direct predecessor, i.e. the set of elements which are smaller than m has a largest element
3. when m has no direct predecessor, i.e. m is a so-called limit-ordinal

Strictly speaking, it is not necessary in transfinite induction to prove the basis, because it is a vacuous special case of the proposition that if P is true of all n < m, then P is true of m. It is vacuously true precisely because there are no values of n < m that could serve as counterexamples. See three forms of mathematical induction for more on this point.

Proof or reformulation of mathematical induction

The principle of mathematical induction is usually stated as an axiom of natural numbers, see Peano axioms. However, it can be proved in some logical systems; for instance, if the following axiom (called the well-ordering principle for natural numbers):

The set of natural numbers is well-ordered

is employed.

The additional axiom is an alternative formulation of principle of mathematical induction. That is, the two are equivalent. See proof of mathematical induction.

External links

• Mathematical Induction, Examples at cut-the-knot

References

• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.1: Mathematical Induction, pp.11–21.

• Mathematical logic
• Proof theory
• Proofs