**One-to-One Grinds**

##### If you feel that you would not be confident if this topic appeared on your exam, we suggest booking one of our **one-to-one grinds!**

## Proof by Induction

**NOTE: Clicking an entry in the right column will take you directly to that question!**

**(BLUE = Paper 1, RED = Paper 2)**

## 2021 Paper 1 Question 4(a)

**(a)** Prove using induction that \(2^{3n-1}\) is divisible by \(7\) for all \(n\in\mathbb{N}\).

The answer is already in the question!

When \(n=1\):

\begin{align}2^{3n-1}+3&=2^{3(1)-1}+3\\&=2^2+3\\&=7\end{align}

which is divisible by \(7\).

Therefore, let us assume that it is true for \(n=k\), i.e. that \(2^{3k-1}+3\) is divisible by \(7\).

Give that it is true for \(n=k\) , we wish to now prove that it is also true for \(n=k+1\), i.e. that \(2^{3(k+1)-1}+3\) is divisible by \(7\).

\begin{align}2^{3(k+1)-1}+3&=2^{3k+3-1}+3\\&=2^{3k+2}+3\\&=2^{3+(3k-1)}+3\\&=2^32^{3k-1}+3\\&=(8)2^{3k-1}+3\\&=(7+1)2^{3k-1}+3\\&=7^{3k-1}+(2^{3k-1}+3)\end{align}

As both terms are divisible by \(7\), \(2^{3(k+1)-1}+3\) is divisible by \(7\), as required.

##### Our **Video Walkthroughs** are in the final stages of editing and will go live during **Summer 2023**.

##### In the meantime, if you feel that you would not be confident if this question (or similar) appeared on your exam, we suggest booking one of our **one-to-one grinds!**

## 2020 Paper 1 Question 7(d)

**(d) **Prove using induction that, for all \(n\in\mathbb{N}\), the sum of the first \(n\) square numbers can be found using the formula:

\begin{align}1^2+2^2+3^2+4^2+…+n^2=\frac{n(n+1)(2n+1)}{6}\end{align}

The answer is already in the question!

When \(n=1\), the right hand side is

\begin{align}\frac{1(1+1)(2(1)+1)}{6}&=\frac{1(2)(3)}{6}\\&=1\end{align}

which is indeed equal to the left hand side of \(1^2\).

Therefore, let us assume that this relation is true for \(n=k\), i.e. that

\begin{align}1^2+2^2+3^2+4^2+…+k^2=\frac{k(k+1)(2k+1)}{6}\end{align}

Using this assumption, we now wish to prove that it is true for \(n=k+1\), i.e. that

\begin{align}1^2+2^2+3^2+4^2+…+k^2+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6}\end{align}

According to our assumption, we can rewrite the left hand side as

\begin{align}1^2+2^2+3^2+4^2+…+k^2+(k+1)^2&=\frac{k(k+1)(2k+1)}{6}+(k+1)^2\\&=\frac{k(k+1)(2k+1)+6(k+1)^2}{6}\\&=\frac{(k+1)[k(2k+1)+6(k+1)]}{6}\\&=\frac{(k+1)(2k^2+7k+6)}{6}\\&=\frac{(k+1)(k+2)(2k+3)}{6}\end{align}

which is indeed equal to the right hand side.

Therefore, the formula is indeed true for all \(n\in\mathbb{N}\).

##### Our **Video Walkthroughs** are in the final stages of editing and will go live during **Summer 2023**.

##### In the meantime, if you feel that you would not be confident if this question (or similar) appeared on your exam, we suggest booking one of our **one-to-one grinds!**

## 2019 Paper 1 Question 2(b)

**(b)** Prove, using induction, that \(3^n\geq 4n+1\), where \(n\geq2\) and \(n\in\mathbb{N}\).

The answer is already in the question!

The inequality is true for \(n=2\) as \(3^2\geq4(2)+1\).

Therefore let, us assume that it is true for \(n=k\), i.e. that

\begin{align}3^k\geq4k+1\end{align}

Using this assumption, we now wish to prove that it is also true for \(n=k+1\), i.e. that

\begin{align}3^{k+1}\geq4k+5\end{align}

First, we will multiply our assumption by \(3\):

\begin{align}3(3^k)\geq3(4k+1)\end{align}

\begin{align}\downarrow\end{align}

\begin{align}3^{k+1}\geq12k+3\end{align}

Since \(12k+3>4k+5\) for \(k\geq2\), it follows that

\begin{align}3^{k+1}\geq4k+5\end{align}

as required.

##### Our **Video Walkthroughs** are in the final stages of editing and will go live during **Summer 2023**.

##### In the meantime, if you feel that you would not be confident if this question (or similar) appeared on your exam, we suggest booking one of our **one-to-one grinds!**

## 2018 Paper 1 Question 4(a)

**(a)** Prove, using induction, that if \(n\) is a positive integer then

\((\cos\theta+i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta)\), where \(i^2=-1\).

The answer is already in the question!

For \(n=1\), the formula states that

\begin{align}(\cos\theta+i\sin\theta)^1=\cos(1\theta)+i\sin(1\theta)\end{align}

\begin{align}\cos\theta+i\sin\theta=\cos\theta+i\sin\theta\end{align}

and therefore it is true for \(n=1\).

Hence, let us assume that it is true for \(n=k\), i.e. that

\begin{align}(\cos\theta+i\sin\theta)^k=\cos(k\theta)+i\sin(k\theta)\end{align}

Using this assumption, we now wish to prove that it is also true for \(n=k+1\), i.e. that

\begin{align}(\cos\theta+i\sin\theta)^{k+1}=\cos[(k+1)\theta]+i\sin[(k+1)\theta]\end{align}

Let us look at the left hand side:

\begin{align}(\cos\theta+i\sin\theta)^{k+1}&=(\cos\theta+i\sin\theta)^{k}(\cos\theta+i\sin\theta)^{1}\\&=[\cos(k\theta)+i\sin(k\theta)](\cos\theta+i\sin\theta)\theta]\\&=[\cos(k\theta)-\sin(k\theta)\sin\theta]+i[\cos(k\theta)\sin\theta+\cos\theta\sin(k\theta)]\\&=\cos[(k+1)\theta]+i\sin[(k+1)\theta]\end{align}

which is indeed the right hand side.

Therefore, the formula is true for all positive integers \(n\).

##### Our **Video Walkthroughs** are in the final stages of editing and will go live during **Summer 2023**.

##### In the meantime, if you feel that you would not be confident if this question (or similar) appeared on your exam, we suggest booking one of our **one-to-one grinds!**

## 2016 Paper 1 Question 4(a)

**(a)** Prove by induction that \(8^n-1\) is divisible by \(7\) for all \(n\in\mathbb{N}\).

The answer is already in the question!

The statement is true for \(n=1\) as \(8^1-1=7\) is divisible by \(7\).

Therefore, let us assume that it is true for \(n=k\), i.e. that \(8^k-1\) is divisible by \(7\).

Using this assumption, we wish to now prove that \(8^{k+1}-1\) is also divisible by \(7\).

\begin{align}8^{k+1}-1&=8(8^k)-1\\&=(7+1)(8^k)-1\\&=7(8^k)+(8^k-1)\end{align}

As both terms are divisible by \(7\), \(8^{k+1}-1\) is divisible by \(7\), as required.