Mathematical induction is a method for proving that a proposition 
holds for every integer 
. The base case establishes 
. For the inductive step, one assumes
,
called the induction hypothesis, for an arbitrary integer 
and proves 
. The principle
of mathematical induction then implies that 
holds for every 
.
For example, consider the identity
 |
The base case 
is immediate. If the identity holds for 
, then
 |
which proves the inductive step.
Ordinary mathematical induction uses the principle of weak induction. Under the principle
of strong induction, the induction hypothesis assumes 
for every 
from 
through 
, while transfinite induction
extends the method from the integers to well-ordered
sets.
