A-level Mathematics/Edexcel/Further 1/Proof by Mathematical Induction

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

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. basis case - Is it true for the first case? This means is it true for the first possible value of n.
  3. Assumption - We assume what we are trying to prove is true for a general number. such as
  4. Induction - Show that if our assumption is true for the ( term, then it must be true for the term after (term.
  5. Conclusion - Formalise your proof.

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

  1. Summing series
  2. Divisibility
  3. Recurrence relations
  4. Matrices

Example of proofs by Induction involving Summing series[edit]

Proposition:

Note our parameter, This means it wants us to prove that it's true for all values of which belong to the set() of positive integers ()

Basis case:


The Left hand side of our equation is equal to the right hand side of our equation, therefore our basis case holds true.

Now you make your assumption:

This is what we are assuming to be true for all values of K which belong to the set of positive integers:

Induction: For the induction we need to utilise the fact we are assuming to be true, as such we can just add on another term to the summation of the term in the series to give us the summation of the term of the series:

Factoring out we get:

 

This gives us:
Note we know that we're finished because, looking at what we were originally asked to prove, the values are replaced with .

Summary:


Therefore, if our assumption is true for then is also true, which implies that is true for all values of that belong to the set of positive integers.

Example of a proof by induction involving Divisibility[edit]

Proposition:

Again, note our parameter, This means it wants us to prove that it's true for all values of which belong to the set() of positive integers ()

Basis case:

Assumption: Now we let where is a general positive integer and we assume that

Remember

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 it implies because you have successfully shown that 4 divides , where is a general, positive integer () and also the consecutive term after the general term ()

Conclusion:

If


Example of recurrence Relations proofs by Induction[edit]

Example of proofs by Induction involving Matrices[edit]

References[edit]