Standard Proofs by Induction (Edexcel International A Level (IAL) Further Maths: Further Pure 1): Revision Note

Prove by induction that $\sum _{r=1}^{n}r\left(r-3\right)=\frac{1}{3}n\left(n-4\right)\left(n+1\right)$ for $n\in {\mathrm{\mathbb{Z}}}^{+}$.

STE P 1: The basic step
Find the LHS when $n=1$

$\sum _{r=1}^{1}r\left(r-3\right)=1\left(1-3\right)=-2$

Find the RHS when $n=1$

$\frac{1}{3}\times 1\times \left(1-4\right)\left(1+1\right)=\frac{1}{3}\times \left(-6\right)=-2$

The LHS and RHS are equal, which shows the statement is true for $n=1$
State this

LHS = RHS, so it is true for $n=1$

STEP 2: The assumption step
Assume the statement is true for some $n=k$ where $k$ is a positive integer

Assume that $\sum _{r=1}^{k}r\left(r-3\right)=\frac{1}{3}k\left(k-4\right)\left(k+1\right)$

STEP 3: The inductive step
Find the RHS when $n=k+1$

$\frac{1}{3}\left(k+1\right)\left(k+1-4\right)\left(k+1+1\right)=\frac{1}{3}\left(k+1\right)\left(k-3\right)\left(k+2\right)$

Find the LHS when $n=k+1$

$\sum _{r=1}^{k+1}r\left(r-3\right)$

Prove that the LHS when $n=k+1$ equals the RHS when $n=k+1$
Start by pulling out the final term in the sum

$\begin{array}{rcl}\sum _{r=1}^{k+1}r\left(r-3\right)& =& \sum _{r=1}^{k}r\left(r-3\right)+\left(k+1\right)\left(k+1-3\right)\\ & =& \sum _{r=1}^{k}r\left(r-3\right)+\left(k+1\right)\left(k-2\right)\end{array}$

Now use the assumption in STEP 2 to replace the sum from 1 to $k$ with its answer

$\begin{array}{rcl}\sum _{r=1}^{k+1}r\left(r-3\right)& =& \frac{1}{3}k\left(k-4\right)\left(k+1\right)+\left(k+1\right)\left(k-2\right)\end{array}$

Now factorise the right-hand side

$\begin{array}{rcl}\sum _{r=1}^{k+1}r\left(r-3\right)& =& \left(k+1\right)\left[\frac{1}{3}k\left(k-4\right)+\left(k-2\right)\right]\\ & =& \frac{1}{3}\left(k+1\right)\left[k\left(k-4\right)+3\left(k-2\right)\right]\end{array}$

Expand inside the square brackets then continue to factorise

$\begin{array}{rcl}\sum _{r=1}^{k+1}r\left(r-3\right)& =& \frac{1}{3}\left(k+1\right)\left[k^2-4k+3k-6\right]\\ & =& \frac{1}{3}\left(k+1\right)\left[k^2-k-6\right]\\ & =& \frac{1}{3}\left(k+1\right)\left(k-3\right)\left(k+2\right)\end{array}$

This is the same as the RHS when $n=k+1$
The LHS and RHS are equal, which shows that the statement is true for $n=k+1$
State this

LHS = RHS, so it is true for $n=k+1$

STEP 4: The conclusion
We have just proved that if the case when $n=k$ is true, then the case when $n=k+1$ is true
We have also shown that the case when $n=1$ is true
Those two parts come together to mean that $n=1$ is true, so $n=2$ is true, so $n=3$ is true, ... and so on

If it is true for $n=k$, then it is true for $n=k+1$.
As it is true for $n=1$, the statement is true for all $n\in {\mathrm{\mathbb{Z}}}^{+}$.

Prove by induction that $\mathrm{f}\left(n\right)=6^n+{13}^{n+1}$ is divisible by 7 for all integers satisfying $n\ge 0$.

STE P 1: The basic step
Prove that it is true for $n=0$

$\begin{array}{rcl}\mathrm{f}\left(0\right)& =& 6^0+{13}^{0+1}\\ & =& 1+13\\ & =& 14\\ & =& 7\times 2\end{array}$

State that it is true for $n=0$

14 is divisible by 7, so it is true for $n=0$

STEP 2: The assumption step
Assume the statement is true for some $n=k$ where $k$ is a positive integer

Assume that $\mathrm{f}\left(k\right)=6^k+{13}^{k+1}$ is divisible by 7

Replace "being divisible by 7" with being equal to $7m$, where $m$ is a positive integer

$6^k+{13}^{k+1}=7m$

STEP 3: The inductive step
Substitute $n=k+1$ into the function

$\begin{array}{rcl}\mathrm{f}(k+1)& =& 6^{k+1}+{13}^{\left(k+1\right)+1}\\ & =& 6^{k+1}+{13}^{k+2}\end{array}$

Now make either $6^k$ or ${13}^{k+1}$ the subject of STEP 2 and substitute it in
It helps to use index laws first

$\begin{array}{rcl}\mathrm{f}(k+1)& =& 6^k\times 6+{13}^{k+2}\\ & =& \left(7m-{13}^{k+1}\right)\times 6+{13}^{k+2}\end{array}$

Simplify the terms, using index laws to group the ${13}^{k+1}$ terms

$\begin{array}{rcl}\mathrm{f}(k+1)& =& 42m-6\times {13}^{k+1}+{13}^{k+2}\\ & =& 42m-6\times {13}^{k+1}+13\times {13}^{k+1}\\ & =& 42m+(-6+13)\times {13}^{k+1}\\ & =& 42m+7\times {13}^{k+1}\end{array}$

The goal is to show that this result is divisible by 7
Factorise out a 7 to show this

$\begin{array}{rcl}\mathrm{f}(k+1)& =& 7\times \left(6m+{13}^{k+1}\right)\end{array}$

State that it is true for $n=k+1$

$\mathrm{f}\left(k+1\right)$ is divisible by 7, so it is true for $n=k+1$

STEP 4: The conclusion
We have just proved that if the case when $n=k$ is true, then the case when $n=k+1$ is true
We have also shown that the case when $n=0$ is true
Those two parts come together to mean that $n=0$ is true, so $n=1$ is true, so $n=2$ is true, ... and so on

If it is true for $n=k$, then it is true for $n=k+1$.
As it is true for $n=0$, the statement is true for all integers $n\ge 0$.

• If the recursive formula involves the previous two terms, then the basic step must be done for both $n=1$ and $n=2$.

A sequence is defined by $u_{n+1}=5u_n-4$ where $u_1=2$ and $n\ge 1$.

Prove by mathematical induction that $u_n=5^{n-1}+1$, where $n\ge 1$.

STE P 1: The basic step
Find $u_1$ from the recursive sequence

$u_1=2$

Find $u_1$ from the n^th term formula

$\begin{array}{rcl}{u}_1& =& 5^{1-1}+1\\ & =& 5^0+1\\ & =& 1+1\\ & =& 2\end{array}$

These two terms are equal
State that it is true for $n=1$

It is true for $n=1$

STEP 2: The assumption step
Assume the formula is true for some $n=k$ where $k$ is a positive integer

Assume that $u_k=5^{k-1}+1$

STEP 3: The inductive step
Use the recursive sequence to write $u_{k+1}$ in terms of $u_k$

$\begin{array}{rcl}{u}_{k+1}& =& 5u_k-4\end{array}$

Replace $u_k$ with the assumption in STEP 2 and simplify

$\begin{array}{rcl}{u}_{k+1}& =& 5\left(5^{k-1}+1\right)-4\\ & =& 5^k+5-4\\ & =& 5^k+1\end{array}$

Check that this is the same as substituting $n=k+1$ into the n^th term formula

$\begin{array}{rcl}{u}_{k+1}& =& 5^{\left(k+1\right)-1}+1\\ & =& 5^k+1\end{array}$

State that the result is true for $n=k+1$

It is true for $n=k+1$

STEP 4: The conclusion
We have just proved that if the case when $n=k$ is true, then the case when $n=k+1$ is true
We have also shown that the case when $n=1$ is true
Those two parts come together to mean that $n=1$ is true, so $n=2$ is true, so $n=3$ is true, ... and so on

If it is true for $n=k$, then it is true for $n=k+1$.
As it is true for $n=1$, the statement is true for all $n\in {\mathrm{\mathbb{Z}}}^{+}$.

The matrix $\mathbf{M}$ is given by $\mathbf{M}=\left(\begin{array}{cc}2& 2\\ 0& 1\end{array}\right)$.

Prove, using mathematical induction, that ${\mathbf{M}}^n=\left(\begin{array}{cc}{2}^n& 2(2^n-1)\\ 0& 1\end{array}\right)$ for all integers satisfying $n\ge 1$.

STE P 1: The basic step
Prove that it is true for $n=1$

$\begin{array}{rcl}{\mathbf{M}}^1& =& \left(\begin{array}{cc}{2}^1& 2\left(2^1-1\right)\\ 0& 1\end{array}\right)\\ & =& \left(\begin{array}{cc}2& 2\\ 0& 1\end{array}\right)\\ & =& \mathbf{M}\end{array}$

State that it is true for $n=1$

It is true for $n=1$

STEP 2: The assumption step
Assume the formula is true for some $n=k$ where $k$ is a positive integer

Assume that ${\mathbf{M}}^k=\left(\begin{array}{cc}{2}^k& 2(2^k-1)\\ 0& 1\end{array}\right)$

STEP 3: The inductive step
Look at the power of $n=k+1$

$\begin{array}{rcl}& & {\mathbf{M}}^{k+1}\end{array}$

Use index laws, then substitute in the assumption from STEP 2

$\begin{array}{rcl}{\mathbf{M}}^{k+1}& =& {\mathbf{M}}^k{\mathbf{M}}^{\mathbf{1}}\\ & =& \left(\begin{array}{cc}{2}^k& 2(2^k-1)\\ 0& 1\end{array}\right)\left(\begin{array}{cc}2& 2\\ 0& 1\end{array}\right)\end{array}$

Use matrix multiplication to work out the right-hand side
Simplify the terms

$\begin{array}{rcl}{\mathbf{M}}^{k+1}& =& \left(\begin{array}{cc}{2}^k\times 2+0& 2^k\times 2+2(2^{k+1}-1)\times 1\\ 0+0& 0+1\end{array}\right)\\ & =& \left(\begin{array}{cc}{2}^{k+1}& 2\times 2^{k+1}-2\\ 0& 1\end{array}\right)\end{array}$

Check that this is the same as substituting $n=k+1$ into the formula for ${\mathbf{M}}^n$

$\begin{array}{rcl}{\mathbf{M}}^{k+1}& =& \left(\begin{array}{cc}{2}^{k+1}& 2(2^{k+1}-1)\\ 0& 1\end{array}\right)\\ & =& \left(\begin{array}{cc}{2}^{k+1}& 2\times 2^{k+1}-2\\ 0& 1\end{array}\right)\end{array}$

State that the result is true for $n=k+1$

It is true for $n=k+1$

STEP 4: The conclusion
We have just proved that if the case when $n=k$ is true, then the case when $n=k+1$ is true
We have also shown that the case when $n=1$ is true
Those two parts come together to mean that $n=1$ is true, so $n=2$ is true, so $n=3$ is true, ... and so on

If it is true for $n=k$, then it is true for $n=k+1$.
As it is true for $n=1$, the statement is true for all $n\in {\mathrm{\mathbb{Z}}}^{+}$.