Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Preparatory Course Mathematics - Basics - Propositional Logic

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 1/9/2017