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

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 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,\ 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:

$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}[k^{2}+4(k+1)]$ 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.$ 