Mathematical induction

From Wikipedia, the free encyclopedia

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.

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:

1 The base case: showing that the statement holds when n = 0.

2 The induction 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.

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 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:

1 Determine if the first lily pad will hold his weight.

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