Encyclopedia > Three forms of mathematical induction

  Article Content

Three forms of mathematical induction

Each proof by mathematical induction has one of three forms.

  • The basis for induction is trivial; the substantial part of the proof goes from case n to case n + 1.
  • The basis for induction is vacuously true; the step that goes from case n to case n + 1 is trivial if n ≥ 2 and impossible if n = 1; the substantial part of the proof is the case n = 2. The case n = 2 is relied on in the trivial induction step.
  • The induction step shows that if P(k) is true for all k < n then P(n) is true; no basis for induction is needed because the first, or basic, case is a vacuously true special case of what is proved in the induction step. It is vacuously true because no value of k is smaller than the smallest possible one. This form works not only when the values of k and n are natural numbers, but also when they are transfinite ordinal numbers; see transfinite induction.

[Examples should be added.]



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
U.S. presidential election, 1804

... (14) Other elections: 1792, 1796, 1800, 1804, 1808, 1812, 1816 Source: U.S. Office of the Federal R ...

 
 
 
This page was created in 40.7 ms