Overview

mathematical induction


Show Summary Details

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

(i)P(1) is true,

(ii) for all 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. For all positive integers2. For all positive integers n, the n-th derivative of 1 x is3. For all positive integers n, (cos θ+i sin θ)n=cos +i sin .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. For all positive integers

2. For all positive integers n, the n-th derivative of 1 x is

3. For all positive integers n, (cos θ+i sin θ)n=cos +i sin .

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

Subjects: Mathematics.


Reference entries

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