A-level Mathematics/Edexcel/Further 1/Proof by Mathematical Induction

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:

$Provethatf(n)=5^n+8n+3isdivisibleby4,forn\in {\mathbb{Z}}^{\mathbb{+}}$

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)$	$Divisibleby4$
$1$	$16$	$4\ast 4$
$2$	$44$	$4\ast 11$
$3$	$152$	$4\ast 38$
$4$	$660$	$4\ast 165$
$5$	$3168$	$4\ast 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: $Provebyinductionthat,\sum _{r=1}^n{r}^3=\frac{1}{4}{n}^2(n+1{)}^2$$,forn\in {\mathbb{N}}^{\mathbb{+}}$

Note our parameter, $forn\in {\mathbb{N}}^{\mathbb{+}}$ 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}}^{\mathbb{+}}$)

Basis case:

$Letn=1$

$\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⟶\sum _{r=1}^n{r}^3=\frac{1}{4}{n}^2(n+1{)}^2,forn=1$

Now you make your assumption:

$Now,letn=kandassumetrue\mathrm{\forall }k\in {\mathbb{Z}}^{\mathbb{+}}$

This is what we are assuming to be true for all values of K which belong to the set of positive integers:

$\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,letn=k+1:\sum _{r=1}^{k+1}{r}^3=\sum _{r=1}^k{r}^3+(k+1{)}^3$

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

$\sum _{r=1}^{k+1}{r}^3=\frac{1}{4}(k+1{)}^2[k^2+4(k+1)]$ 

This gives us: $\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 trueforn=k+1⟶true\mathrm{\forall }n\in {\mathbb{Z}}^{\mathbb{+}}$
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: $Provethat4|f(n)=5^n+8n+3,forn\in {\mathbb{N}}^{\mathbb{+}}$

Again, note our parameter, $forn\in {\mathbb{N}}^{\mathbb{+}}$ 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}}^{\mathbb{+}}$)

Basis case:

$Letn=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 $letn=k+1\to 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),\mathrm{\forall }n\in {\mathbb{Z}}^{\mathbb{+}}$

$If4dividesf(k)(asweassumed)thenitisimpliesthat4alsodividesf(k+1),$
$therefore4dividesf(n),forallvaluesofnthatbelongtothesetofpositiveintegers.$