# 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:
$Prove\ that\ f(n)=5^{n}+8n+3\ is\ divisible\ by\ 4,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)$ | $Divisible\ by\ 4$ |
| $1$ | $16$ | $4*4$ |
| $2$ | $44$ | $4*11$ |
| $3$ | $152$ | $4*38$ |
| $4$ | $660$ | $4*165$ |
| $5$ | $3168$ | $4*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?
* basis 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$
* 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.
* 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 proofs by Induction involving Summing series

Proposition: $Prove\ by\ induction\ that,\displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2}$$,for\ n\in \mathbb {N^{+}}$
Note our parameter, $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:
$Let\ n=1\$
$\displaystyle \sum _{r=1}^{1}r^{3}=1^{3}\ [LHS]$
${\frac {1}{4}}1^{2}(1+1)^{2}=1\ [RHS]$
The Left hand side of our equation is equal to the right hand side of our equation, therefore our basis case holds true.
$LHS=RHS\longrightarrow \displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2},for\ n=1$
Now you make your assumption:
$Now,\ let\ n=k\ and\ assume\ true\ \forall \ k\in \mathbb {Z^{+}}$
This is what we are assuming to be true for all values of K which belong to the set of positive integers:
$\displaystyle \sum _{r=1}^{k}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}$
Induction: For the induction we need to utilise the fact we are assuming $n=k$ to be true, as such we can just add on another term $(k+1)$ to the summation of the $k^{th}$ term in the series to give us the summation of the $(k+1)^{th}$ term of the series:
$Hence,\ let\ n=k+1:\displaystyle \sum _{r=1}^{k+1}r^{3}=\displaystyle \sum _{r=1}^{k}r^{3}+(k+1)^{3}$
$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}+(k+1)^{3}$
Factoring out ${\frac {1}{4}}(k+1)^{2}$ we get:
This gives us: $\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}(k+2)^{2}$
Note we know that we're finished because, looking at what we were originally asked to prove, the $n$ values are replaced with $k+1$.
Summary:
$\therefore \ true\ for\ n=k+1\longrightarrow \ true\ \forall \ n\in \mathbb {Z^{+}}$
Therefore, if our assumption is true for $n=k$ then $n=k+1$ is also true, which implies that $n$ is true for all values of $n$ that belong to the set of positive integers.

## Example of a proof by induction involving Divisibility

Proposition: $Prove\ that\ 4\ |\ f(n)=5^{n}+8n+3,\ for\ n\in \mathbb {N^{+}}$
Again, note our parameter, $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:
$Let\ n=1$
$f(1)=5^{1}+8(1)+3\Rightarrow f(1)=16$
$\therefore \ 4\ |\ f(1)$
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 $let\ n=k+1\rightarrow \ 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)$
$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)$
Now we've shown $4\ |\ f(k+1)-f(k)$ 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:
If $4\ |\ f(k)\Rightarrow 4\ |\ f(k+1)$
$\therefore \ 4\ |\ f(n),\forall \ n\in \mathbb {Z^{+}}$
$If\ 4\ divides\ f(k)\ (as\ we\ assumed)\ then\ it\ is\ implies\ that\ 4\ also\ divides\ f(k+1),$ $therefore\ 4\ divides\ f(n),\ for\ all\ values\ of\ n\ that\ belong\ to\ the\ set\ of\ positive\ integers.$

## References

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