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:

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

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