# 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:
* Proposition – What are you trying to prove?
* Base case – Is it true for the first case? This means is it true for the first possible value of $n$.
* Assumption – We assume what we are trying to prove is true for a general number. such as $k$, also known as the induction hypothesis.
* Induction – Show that if our assumption is true for the ($k^{th})$ term, then it must also be true for the ($k+1^{th})$ term.
* Conclusion – Formalise your proof.
There will be four types of mathematical induction that you will come across in FP1:
* Summation of series;
* Divisibility;
* Recurrence relations;
* Matrices.

## Example of a proof by summation of series

(Empty)

## Example of a proof by divisibility

Proposition: ${\text{Prove that }}4~|~f(n)=5^{n}+8n+3,{\text{ for }}n\in \mathbb {N} ^{+}$
Notice our parameter, ${\text{for }}n\in \mathbb {N} ^{+}$ . This means that what we want to prove must be true for all values of $n$ which belong to the set (denoted by $\in$) of positive integers ($\mathbb {N} ^{+}$).
Base 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 (Induction Hypothesis): Now we let $n=k$ where $k$ is a general positive integer, and we assume that $4\ |\ f(k)$.
Remember that $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~|~{\biglf(k+1)-f(k){\bigr )}$ and thus $4~|~f(k+1)$. This implies that $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 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}}$

## Example of a proof by recurrence relations

(Empty)

## Example of a proof by matrices

(Empty)

## References

* ↑ https://en.wikipedia.org/wiki/Mathematical_induction