Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers.

To proof the formula A(n) for all natural numbers nm, two steps are necessary:

1. the base case, to show that A(m) is true.

2. the inductive step, show that if A(n) holds, then also A(n+1) for nm holds.

Usually applies m=0 or m=1. In special cases can be m>1.

Example: The proof of 1+2+3+…+n.