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.