Proof by Mathematical Induction

Proof by mathematical induction[1]

edit

Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of   within given parameters. For example:

 

We are asked to prove that   is divisible by 4. We can test if it's true by giving   values.

     
     
     
     
     
     

So, the first 5 values of n are divisible by 4, but what about all cases? That's where mathematical induction comes in.

Mathematical induction is a rigorous process, as such all proofs must have the same general format:

  1. Proposition – What are you trying to prove?
  2. Base case – Is it true for the first case? This means is it true for the first possible value of  .
  3. Assumption – We assume what we are trying to prove is true for a general number. such as  , also known as the induction hypothesis.
  4. Induction – Show that if our assumption is true for the (  term, then it must also be true for the (  term.
  5. Conclusion – Formalise your proof.

There will be four types of mathematical induction that you will come across in FP1:

  1. Summation of series;
  2. Divisibility;
  3. Recurrence relations;
  4. Matrices.

Example of a proof by summation of series

edit

(Empty)

Example of a proof by divisibility

edit

Proposition:  

Notice our parameter,   . This means that what we want to prove must be true for all values of   which belong to the set (denoted by  ) of positive integers ( ).

Base case:

 

Assumption (Induction Hypothesis): Now we let   where   is a general positive integer, and we assume that  .

Remember that  .

Induction: Now we want to prove that the   term is also divisible by 4

Hence: 

This is where our assumption comes in, if   then 4 must also divide  .

So:  

 

Now we've shown   and thus  . This implies that   because you have successfully shown that 4 divides  , where   is a general, positive integer ( ) and also the consecutive term after the general term ( )

Conclusion:

 

 

Example of a proof by recurrence relations

edit

(Empty)

Example of a proof by matrices

edit

(Empty)

References

edit