Proof By Induction
Proof By Induction – Proof of \sum r
The general method used for proof by induction is to start proving that it is true for n = 1. Then it is assumed that the statement is also true for n = k. The aim is to show that it is also true for n = k + 1. If this is so then it must be also true for all positive integers of n.
Prove:
\sum_{r=1}^n r=\frac{1}{2} n(n+1)First check if the statement is true for when n = 1
Left hand side:
\sum_{r=1}^1 r=1Right hand side:
\frac{1}{2}(1)(1+1)=1The statement is therefore true when n =1.
We will now assume that it is true for when n = k, in other words:
\sum_{r=1}^k r=\frac{1}{2} k(k+1)Next we need to try and show that if it is true for n = k then it is also going to be true for n = k + 1
When n = k + 1 we have:
\sum_{r=1}^{k+1} rProof By Induction - What is this going to look like?
In general what we are hoping for is that where there is an ‘n’ this is replaced by ‘k + 1’
\sum_{r=1}^{k+1} r=\sum_{r=1}^k r+(k+1) \text { th term }In other words we are just adding the k+1th term
\sum_{r=1}^{k+1} r=\sum_{r=1}^k r+(k+1)The summation of \sum_{r=1}^k r was assumed true for n=k
\begin{aligned} & \sum_{r=1}^{k+1} r=\frac{1}{2} k(k+1)+(k+1) \\ & =\frac{1}{2}(k+1)[k+2] \\ & =\frac{1}{2}(k+1)[(k+1)+1] \end{aligned}And this is of the form \frac{1}{2} n(n+1)
Proof By Induction - Other standard results
There are two other main standard results that can also be proved by induction in a similar way to the above.
\begin{aligned} &\sum r^2=\frac{1}{6} n(n+1)(n+2)\\ &\sum r^3=\frac{1}{4} n^2(n+1)^2 \end{aligned}
Proof By Induction – Other Examples
\text { Prove } \sum_{r=1}^n 2^r=2^{n+1}-2The same process is always applied when proving by induction:
- Test it is true for n = 1
- Assume it is true for n = k
- Test it is true for n = k + 1
So the above is true for when n = 1
Next we assume that it is true for n = k:
\sum_{r=1}^k 2^r=2^{k+1}-2Finally we need to show that it is also true for n = k + 1
\begin{aligned} & \sum_{r=1}^{k+1} 2^r=\sum_{r=1}^k 2^r+(k+1) \text { th term } \\ & =\sum_{r=1}^k 2^r+2^{k+1} \\ & =2^{k+1}-2+2^{k+1} \\ & =2\left(2^{k+1}\right)-2 \\ & =2^{k+2}-2 \\ & \sum_{r=1}^{k+1} 2^r=2^{(k+1)+1}-2 \end{aligned}So it is true for n = k + 1 and therefore it is true for all values of n.
Proof By Induction – Recurrence Relationships
Example
Given u_1=8 \text { and } u_{n+1}=4 u_n-9 n \text { prove } u_n=4^n+3 n+1
Solution
First we will test the statement with n = 1:
u_1-4+3+1-8So the statement s true when n = 1
Next assume that it is true for when n = k
i.e. u_k=4^k+3 k+1
Next we will show that this is true for n = k + 1
\begin{aligned} & u_{k+1}-4 u_k-9 k \\ & =4\left(4^k+3 k+1\right)-9 \mathrm{k} \\ & =4^{k+1}+12 k+4-9 k \\ & =4^{k+1}+3 k+4 \\ & =4^{k+1}+3(k+1)+1 \end{aligned}Therefore the statement is true for n = k + 1 and so all positive values.
Proof By Induction – Divisibility And Multiplication
Example
Show that 3^{2 n}-1 is divisible by 8 for all positive integers
Solution
Just like other induction problems that we have seen so far we show that it is true for n = 1, we then assume it is true for n = k and then we show that it is true for n = k + 1
Let f(n)=3^{2 n}-1
So f(1)=3^2-1=8
And so the statement is true for n = 1
We assume it is true for n = k
i.e. f(k)=3^{2 k}-1
Now we need to show that it is also true for n = k + 1
In order to do this we consider f(k + 1) – f(k)
\begin{aligned} & =\left[3^{2(k+1)}-1\right]-\left[3^{2 k}-1\right] \\ & =3^{2 k+2}-1-3^{2 k}+1 \\ & =3^{2 k}\left[3^2-1\right] \\ & =8\left(3^{2 k}\right) \end{aligned}And it is clear to see that we have shown that for n = k + 1 our statement is divisible by 8.
Proof by induction is generally kept for the A Level Further Maths curriculum. But this was just a flavour of what you can expect if you want to pursue this additional qualification.