## Quick Reference

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*P*(1) is true,*k*, *P*(*k*) implies *P*(*k*+1),then *P*(*n*) is true for all positive integers *n*.

*P*(1) is true,

*k*, *P*(*k*) implies *P*(*k*+1),

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:**1.****2.***n*, the *n*-th derivative of 1 *x* is**3.***n*, (cos *θ*+*i* sin *θ*)^{n}=cos *nθ*+*i* sin *nθ*.In each case, it is clear what the proposition *P*(*n*) should be, and that (i) can be verified. The method by which the so-called induction step (ii) is proved depends upon the particular result to be established.

**1.**

**2.***n*, the *n*-th derivative of 1 *x* is

**3.***n*, (cos *θ*+*i* sin *θ*)^{n}=cos *nθ*+*i* sin *nθ*.

A modified form of the principle is this. Let there be associated, with each integer *n*≥*n*_{0}, a proposition *P*(*n*), which is either true or false. If (i) *P*(*n*_{0}) is true, and (ii) for all *k*≥*n*_{0}, *P*(*k*) implies *P*(*k*+1), then *P*(*n*) is true for all integers *n*≥*n*_{0}. This may be used to prove, for example, that 3^{n}>*n*^{3} for all integers *n*≥4.

*Subjects:*
Mathematics.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.