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.
