Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag

Mathematics-Online course: Basic Mathematics - Natural Numbers

Mathematical Induction

[previous page] [next page] [table of contents][page overview]

Statements with natural numbers as their parameters can be proved by the Principle of Mathematical Induction. If $ A(n)$ is a statement that depends on $ n\in\mathbb{N}$, the method of proof consists of the following two steps:

This establishes the truth of $ A(n)$ for all $ n\in\mathbb{N}$ .

The Principle of Mathematical Induction successively infers the truth of a statement $ A(n+1)$ from the previous statement $ A(n)$. Therefore, if in the base step $ A(n_0)$ is verfied for some $ n_0>1$ rather than $ A(1)$, then the statement has only been proved for $ n \geq n_0$.

(Authors: Kimmerle/Abele)

The formula for the sum of square numbers,

$\displaystyle A(n):\
\sum_{i=1}^{n} i^2 = 1^2+2^2+\dots+n^2= \frac{1}{6}n(n+1)(2n+1)

can be proved by Mathematical Induction.

Base step ($ A(1)$):

$\displaystyle \sum_{i=1}^{1} i^2 = 1^2 = \frac{1\cdot2\cdot3}{6}

Conclusion ( $ A(n)\implies A(n+1))$:

$\displaystyle \sum_{i=1}^{n+1} i^2$ $\displaystyle =$ $\displaystyle \sum_{i=1}^{n} i^2 + (n+1)^2
= \underbrace{\displaystyle\frac{n(n+1)(2n+1)}{6}}_{
A(n)} + (n+1)^2$  
  $\displaystyle =$ $\displaystyle \displaystyle\frac{(n+1)\big[n(2n+1)+6(n+1)\big]}{6}
= \displaystyle\frac{(n+1)(n+2)(2n+3)}{6}\,.$  

As indicated, the induction hypothesis has been applied to obtain the third equality.

(Authors: Kimmerle/Abele)

[previous page] [next page] [table of contents][page overview]

  automatically generated 10/31/2008