Encyclopedia > Proof of mathematical induction

  Article Content

Proof of mathematical induction

It is possible to prove that mathematical induction works using a form of natural deduction logic[?] and using proof by contradiction.

A simplified version is given here. This proof does not use the standard mathematical symbols for there exists and for all to make it more accessible to less mathematically motivated readers.

Suppose

      P(0)                                 [1]

and

      For all n >=0, P(n) => P(n+1)        [2]

Consider also the statement

      For all m >=0, P(m)                  [3]

- in other words P is true for all integer values of m.

Assume this is false, which is equivalent to

      There exists an m such that not P(m) [4]

The proof hinges on showing that if [1] and [2] hold, then [4] is false, hence [3].

Assume [1], [2] and [4].

Using [4], let m' be the smallest such value such that not P(m), hence not P(m')

Clearly m' cannot be 0, since this leads to an immediate contradiction [ P(0) & not P(0] with P(0) - rule [1]

Suppose m'>0.

From the definition of m', P(m'-1), hence by [2] P(m'). This also gives a contradiction [P(m') & not P(m')] since we are assuming not P(m').

It thus follows that [1] and [2] together imply not [4], which we have already established is just [3].

Hence if

     P(0)              [1]

and

     P(n) => P (n+1)   [2] 

it follows that (with a trivial change of variable)

     for all n >=0, P(n)   [3],

which is the principle of mathematical induction.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
North Haven, New York

... average household size is 2.20 and the average family size is 2.77. In the village the population is spread out with 17.4% under the age of 18, 3.5% from 18 to 24, 22.3% ...

 
 
 
This page was created in 27.4 ms