A process for proving mathematical statements involving members of an ordered
set (possibly infinite). There are various formulations of the principle of
induction. For example, by the principle of finite induction, to prove a
statement p(i) is true for all integers i ≥ i0 , it suffices to prove that
(a) P(i0) is true;
(b) for all k ≥ i0 , the assumption that P(k) is true (the induction hypothesis)
implies the truth of P(k+1).
(a) is called the basis of the proof, (b) is the induction step.
Generalizations are possible. Other forms of induction permit the induction step
to assume the truth of P(k) and also that of
P(k-1), P(k-2), ...., P(k-i)
for suitable i. Statements of several variables can also be considered.