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
Quackery

... medicine. Quackery is still abundant today, herbal medicine[?], miracle cures, and diet and fitness regimes are considered a form of Quackery by medical experts, ...

 
 
 
This page was created in 39.4 ms