Mathematics-Online course: Basic Mathematics-Natural Numbers-Mathematical Induction

	[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]
	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 is a statement that depends on $n\in\mathbb{N}$ , the method of proof consists of the following two steps:

Base step (also referred to as initial step): Verify that is true.
Conclusion (also referred to as inductive step): Show that the assumption ,, is true`` (induction hypothesis) implies the truth of , i.e.

$\displaystyle A(n) \implies A(n+1) \,.$

This establishes the truth of

for all $n\in\mathbb{N}$ .

The Principle of Mathematical Induction successively infers the truth of a statement from the previous statement . Therefore, if in the base step is verfied for some rather than , 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 ():

$\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