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
Royalist

... At its simplest, it refers to an adherent of a monarch or royal family. Of the more specific uses of the term, the most common include: 1. A supporter of King ...

 
 
 
This page was created in 36 ms