Proof by mathematical induction

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

${\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 $f(n)$  is divisible by 4. We can test if it's true by giving $n$  values.

$n$  $f(n)$  ${\text{Divisible by }}4$
$1$  $16$  $4\cdot 4$
$2$  $44$  $4\cdot 11$
$3$  $152$  $4\cdot 38$
$4$  $660$  $4\cdot 165$
$5$  $3168$  $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. 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 $k$
4. Induction – Show that if our assumption is true for the ($k^{th})$  term, then it must be true for the term after ($k+1^{th})$  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 a proof by divisibility

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

Note our parameter, ${\text{for }}n\in \mathbb {N} ^{+}$  This means it wants us to prove that it's true for all values of $n$  which belong to the set ($\in$ ) of positive integers ($\mathbb {N} ^{+}$ )

Basis case:

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

Assumption: Now we let $n=k$  where $k$  is a general positive integer and we assume that $4\ |\ f(k)$

Remember $f(k)=5^{k}+8k+3$

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

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

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

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

{\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 $4~|~{\bigl (}f(k+1)-f(k){\bigr )}$  and thus $4~|~f(k+1)$  it implies $4~|~f(n)$  because you have successfully shown that 4 divides $f(n)$ , where $n$  is a general, positive integer ($k$ ) and also the consecutive term after the general term ($k+1$ )

Conclusion:

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

{\begin{aligned}&{\text{If }}4{\text{ divides }}f(k){\text{ (as we assumed) then it is 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}}