Mathematical induction

From Wikipedia, the free encyclopedia

• Find out more about navigating Wikipedia and finding information •

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. 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

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Indeed, the validity of mathematical induction is logically equivalent to the well-ordering principle.

Mathematical induction should not be misconstrued as a form of inductive reasoning, which is considered non-rigorous in mathematics. (See Problem of induction.) In fact, mathematical induction is a form of deductive reasoning and is fully rigorous.

[hide]

[edit] History

The earliest traces of mathematical induction can be found in Euclid's proof that the number of primes is infinite and in Bhaskara II's "cyclic method".^[1] A form of proof by mathematical induction appears in a book written by Al-Karaji around 1000AD, who used it to prove the binomial theorem, Pascal's triangle, and the sum of integral cubes.^[2]^[3] Shortly afterwards, Ibn al-Haytham (Alhazen) used the inductive method to prove the sum of fourth powers, and by extension, the sum of any integral powers, which was an important result in integral calculus.^[4]^[5] He only stated it for particular integers, but his proof for those integers was by induction and generalizable.^[4]

None of these ancient mathematicians explicitly gave the inductive hypothesis. The first rigorous exposition of the principle of induction was given by Francesco Maurolico, in his Arithmeticorum libri duo (1575), who used the technique to prove that the sum of the first n odd integers is n². Induction was also discovered independently by the Swiss Jakob Bernoulli, and the Frenchmen Pascal and Fermat.^[1]

[edit] Description

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

The basis: showing that the statement holds when n = 0.
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" in the inductive step is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis (that the statement is true for n = m) and then uses this assumption to prove the statement for n = m + 1.

A formal description of mathematical induction can be illustrated by reference to the sequential effect of falling dominoes.

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:

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

then you can conclude that all of the dominoes will fall, and this fact is inevitable.

Another analogy can be to consider an infinite set of identical lily pads, all equally spaced on a pond. If a frog wishes to traverse the pond, he must:

Determine if the first lily pad will hold his weight.
Prove that he can jump from one lily pad to another.

Thus, he can conclude that he can jump to all of the lily pads.

[edit] Axiom of Induction

The basic assumption or axiom of induction (accepted not proved) is, in logical symbols,

$\forall \mbox{ predicates }P,\, (P(0) \land \forall k [P(k) \Rightarrow P(k+1)]) \Rightarrow \forall n P(n)$

where P is the proposition in question and n is a natural number.

Step 1. prove P(0) - the formula holds for integer 0.
Step 2. prove that for all (or any) natural number k, P(k) implies P(k + 1). To do this one assumes P(k) and shows that it implies P(k + 1). This does not mean substituting (k + 1) into P(k) - this is a very common mistake, which consists in assuming what is to be proved. Together 1 and 2 imply that P(n) holds for all n greater than or equal to 0.

[edit] Example

Suppose we wish to prove the statement:

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

for all natural numbers n; call this statement P(n). (This is a special case of Faulhaber's formula.) This is a simple formula for the sum of the positive natural numbers less than or equal to number n. The proof that the statement is true for all natural numbers n proceeds as follows.

Check if it is true for n = 1. The sum of 1 and no other number is simply 1. And 1(1 + 1) / 2 = 1. So the statement is true for n = 1. 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.,

$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 does not change the equality:

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

By algebraic manipulation we have for the right-hand side

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

Thus we have

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

Notice that this is equivalent to the assertion made by P(m + 1). This proof is conditional: we made the assumption that P(m) is true, and from that we derived P(m + 1). Thus, if P(m) is true, P(m + 1) must also be true. Symbolically, we have shown that

$P(m) \Rightarrow P(m + 1).\,$

Now, to finish, we use the process of mathematical induction:

We know P(1) is true by substituting in 1 for n.
Since P(1) implies P(1 + 1), we get P(2).
Similarly, since P(2) implies P(2 + 1), we get P(3).
With P(3), P(4) follows.
From P(4), we get P(5).
Etc. (Here is where the axiom of mathematical induction comes in.)
We may conclude that P(n) holds for any natural number n. Q.E.D.

Euclideanelements

Monday, September 10, 2007