# Proof by mathematical induction[1]

Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of ${\displaystyle n}$  within given parameters. For example:

${\displaystyle {\text{Prove that }}f(n)=5^{n}+8n+3{\text{ is divisible by }}4,{\text{ for }}n\in \mathbb {Z} ^{+}}$

We are asked to prove that ${\displaystyle f(n)}$  is divisible by 4. We can test if it's true by giving ${\displaystyle n}$  values.

${\displaystyle n}$  ${\displaystyle f(n)}$  ${\displaystyle {\text{Divisible by }}4}$
${\displaystyle 1}$  ${\displaystyle 16}$  ${\displaystyle 4\cdot 4}$
${\displaystyle 2}$  ${\displaystyle 44}$  ${\displaystyle 4\cdot 11}$
${\displaystyle 3}$  ${\displaystyle 152}$  ${\displaystyle 4\cdot 38}$
${\displaystyle 4}$  ${\displaystyle 660}$  ${\displaystyle 4\cdot 165}$
${\displaystyle 5}$  ${\displaystyle 3168}$  ${\displaystyle 4\cdot 792}$

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 ${\displaystyle n}$ .
3. Assumption – We assume what we are trying to prove is true for a general number. such as ${\displaystyle k}$ , also known as the induction hypothesis.
4. Induction – Show that if our assumption is true for the (${\displaystyle k^{th})}$  term, then it must also be true for the (${\displaystyle k+1^{th})}$  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.

(Empty)

## Example of a proof by divisibility

Proposition: ${\displaystyle {\text{Prove that }}4~|~f(n)=5^{n}+8n+3,{\text{ for }}n\in \mathbb {N} ^{+}}$

Notice our parameter, ${\displaystyle {\text{for }}n\in \mathbb {N} ^{+}}$  . This means that what we want to prove must be true for all values of ${\displaystyle n}$  which belong to the set (denoted by ${\displaystyle \in }$ ) of positive integers (${\displaystyle \mathbb {N} ^{+}}$ ).

Base case:

{\displaystyle {\begin{aligned}&{\text{Let }}n=1\\&f(1)=5^{1}+8(1)+3\implies f(1)=16\\&\therefore 4~|~f(1)\end{aligned}}}

Assumption (Induction Hypothesis): Now we let ${\displaystyle n=k}$  where ${\displaystyle k}$  is a general positive integer, and we assume that ${\displaystyle 4\ |\ f(k)}$ .

Remember that ${\displaystyle f(k)=5^{k}+8k+3}$ .

Induction: Now we want to prove that the ${\displaystyle k+1^{th}}$  term is also divisible by 4

Hence:${\displaystyle {\text{let }}n=k+1\implies f(k+1)=5^{k+1}+8(k+1)+3}$

This is where our assumption comes in, if ${\displaystyle 4~|~f(k)}$  then 4 must also divide ${\displaystyle f(k+1)-f(k)}$ .

So: ${\displaystyle f(k+1)-f(k)=5^{k+1}+8(k+1)+3-(5^{k}+8k+3)}$

{\displaystyle {\begin{aligned}&f(k+1)-f(k)=5(5^{k})-5^{k}+8\\&f(k+1)-f(k)=4(5^{k})+8\\&\therefore ~f(k+1)-f(k)=4(5^{k}+2)\end{aligned}}}

Now we've shown ${\displaystyle 4~|~{\bigl (}f(k+1)-f(k){\bigr )}}$  and thus ${\displaystyle 4~|~f(k+1)}$ . This implies that ${\displaystyle 4~|~f(n)}$  because you have successfully shown that 4 divides ${\displaystyle f(n)}$ , where ${\displaystyle n}$  is a general, positive integer (${\displaystyle k}$ ) and also the consecutive term after the general term (${\displaystyle k+1}$ )

Conclusion:

{\displaystyle {\begin{aligned}&4~|~f(k)\implies 4~|~f(k+1)\\&\therefore ~4~|~f(n),\forall n\in \mathbb {Z} ^{+}\end{aligned}}}

{\displaystyle {\begin{aligned}&{\text{If }}4{\text{ divides }}f(k){\text{ (as we assumed) then it implies that }}4{\text{ also divides }}f(k+1)\\&{\text{therefore }}4{\text{ divides }}f(n),{\text{ for all values of }}n{\text{ that belong to the set of positive integers.}}\end{aligned}}}

(Empty)

(Empty)