The method of proof ‘by mathematical induction’ is based on the following principle:
Principle of mathematical induction
Let there be associated, with each positive integer n, a proposition P(n), which is either true or false. If
This essentially describes a property of the positive integers; either it is accepted as a principle that does not require proof or it is proved as a theorem from some agreed set of more fundamental axioms. The following are typical of results that can be proved by induction:
A modified form of the principle is this. Let there be associated, with each integer n≥n0, a proposition P(n), which is either true or false. If (i) P(n0) is true, and (ii) for all k≥n0, P(k) implies P(k+1), then P(n) is true for all integers n≥n0. This may be used to prove, for example, that 3n>n3 for all integers n≥4.