# 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:

- Proposition – What are you trying to prove?
- basis case – Is it true for the first case? This means is it true for the first possible value of .
- Assumption – We assume what we are trying to prove is true for a general number. such as
- Induction – Show that if our assumption is true for the ( term, then it must be true for the term after ( term.
- Conclusion – Formalise your proof.

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

- Summing series
- Divisibility
- Recurrence relations
- Matrices

## Example of a proof by summation of series[edit]

## Example of a proof by divisibility[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:

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: