A-level Mathematics/OCR/FP1/Mathematical Induction

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