Course Content
Higher Level (by year)
0/17
Higher Level (by topic)
0/13
Ordinary Level (by year)
0/17
Ordinary Level (by topic)
0/12
Past Papers

## Proof by Induction

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

(BLUE = Paper 1, RED = Paper 2)

Since 2015, the following subtopic... Has explicitly appeared in...

Series Proofs

Trigonometric Proofs

Divisibility Proofs

Inequality Proofs

## 2021 Paper 1 Question 4(a)

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

Solution

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.

Video Walkthrough

## 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}

Solution

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

Video Walkthrough

## 2019 Paper 1 Question 2(b)

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

Solution

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.

Video Walkthrough

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

Solution

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

Video Walkthrough

## 2016 Paper 1 Question 4(a)

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

Solution

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.

Video Walkthrough