A-level Mathematics/OCR/FP1/Mathematical Induction

From Wikibooks, open books for an open world
Jump to: navigation, search

Proof by induction is a method of deductive reasoning that produces a fully rigorous mathematical proof:

  • Step 1 Prove that the result is true for a starting value, such as . This is called the basis case.
  • Step 2 Assume that the result is true for some value,
  • Step 3 Prove that if it is true for , it is true for .
  • Step 4 Conclude that the proposition is true for all positive integers.

Since we have proved the result for a general value, , then if we prove it for the next value, , we can logically conclude that it will be true for the next value, and the next, and the next, and so on ad infinitum.

An Example[edit]

Prove that the sequence:

Step 1: when  : LHS = , RHS = . Therefore, we have proved the hypothesis for one value...

Step 2: Now let , and prove this.

Let us use the symbol to represent the series

However, also represents (which is the same series, but in a different order)

If we add the two series together, we get:

Step 3: Now let :

However, the part in italics of the above line, is already known. Thus:

When we expand the left hand side, we get:

Step 4 The left hand side of the equation is equal to the right hand side, so therefore we can conclude that, by the principle of mathematical induction, since it is true for , and since if it is true for then it is true for , it is true for any positive integer.

Another Example[edit]

Prove that the sequence:

Step 1:

Prove true when

LHS = RHS therefore true

Step 2:

Assume true when

Step 3:

Prove true when

We have assumed that is true. So we can now assume that

will also be true. However this time we need to prove it as well. This bit can get confusing, but all we have to rearrange each side so that we can see they are equal.

(LHS: took out a factor of ) (RHS: nothing)
(LHS: expanded the brackets) (RHS: simplified the brackets)
(LHS: factorized brackets) (RHS: nothing)

RHS = LHS therefore true

This is part of the FP1 (Further Pure Mathematics 1) module of the A-level Mathematics text.