# Proof by induction

## Introduction

In FP1 you are introduced to the idea of proving mathematical statements by using induction.

Proving a statement by induction follows this logical structure

1. If the statement is true for some $n=k$, it is also true for $n=k+1$.
2. The statement is true for $n=1$.
3. Therefore it is true for 1, 2, 3, 4, 5, ... and for all the natural numbers $n$.

When answering questions on proof by induction you actually work in a different order. You first have to do some rough work - the three steps I've put above are what you need to put at the end of your answer.

Do your rough work in this order

1. Firstly show that the statement holds for $n=1$. Just sub in $n=1$ to whatever you're asked to prove.
2. Then sub in $n=k$ and write down the statement in that form.
3. Then let $n=k+1$ and, using the $n=k$ formula you've written in the above step, prove it is also true.

Then you write the proof bit of your answer at the end. In FP1 they are really strict on how you word your answers to proof by induction questions. This is to get you used to the idea of a rigorous proof that holds water.

Don't worry though. In the numerous examples below I will write down exactly what you need to write to get the full marks for this type of question.

Students often get confused about the logic of induction. The way to think of it is

"Suppose this statement were true for some number $k$. Then it has to also be true for $k+1$."

We're not just saying "it's true", we're saying "suppose it were true for some number $k$". That way if we do find a number that it's true for, we're done.

You need to know the induction proofs for various cases. So in each of the following sections I will just write down the types of proofs you need to know for the exam.

You don't need to memorise each individual step, in fact I recommend you don't do that. Instead get a feel for the method, practice some questions of your own, and you will be able to do these yourself using simple algebra.

## Series

### The sum of the first $n$ natural numbers

Q) Prove that $\sum_{r=1}^{n} r= \frac{n(n+1)}{2}$ by induction.

A) First show that the formula holds for $n=1$ $$\sum_{r=1}^{1} r = 1 = \frac{1(1+1)}{2} = \frac{2}{2} = 1$$ Suppose the formula holds for some $n=k$ $$\sum_{r=1}^{k} r = \frac{k(k+1)}{2}$$ Then let $n=k+1$ \begin{align} \sum_{r=1}^{k+1} r &= \sum_{r=1}^{k}r + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{k(k+1)+ 2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

### The sum of the squares of the first $n$ natural numbers

Q) Prove that $\sum_{r=1}^{n} r^{2} = \frac{1}{6}n(n+1)(2n+1)$ by induction.

A) First show that the formula holds for $n=1$ $$\sum_{r=1}^{1} r^{2} = 1 = \frac{1}{6}\times 1\times(1+1)(2\times 1+1) = \frac{1}{6}\times 6 = 1$$ Suppose the formula holds for some $n=k$ $$\sum_{r=1}^{k} r^{2} = \frac{1}{6}k(k+1)(2k+1)$$ Then let $n=k+1$ \begin{align} \sum_{r=1}^{k+1} r^{2} &= \sum_{r=1}^{k}r^{2} + (k+1)^{2} \\ &= \frac{1}{6}k(k+1)(2k+1) + (k+1)^{2} \\ &= \frac{1}{6}(k+1)(k(2k+1)+6(k+1)) \\ &= \frac{1}{6}(k+1)(2k^{2}+7k+6) \\ &= \frac{1}{6}(k+1)(k+2)(2k+3) \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

### The sum of the cubes of the first $n$ natural numbers

Q) Prove that $\sum_{r=1}^{n} r^{3} = \frac{1}{4}n^{2}(n+1)^{2}$ by induction.

A) First show that the formula holds for $n=1$ $$\sum_{r=1}^{1} r^{3} = 1 = \frac{1}{4}1^{2}(1+1)^{2} = \frac{4}{4} = 1$$ Suppose the formula holds for some $n=k$ $$\sum_{r=1}^{k} r^{3} = \frac{1}{4}k^{2}(k+1)^{2}$$ Then let $n=k+1$ \begin{align} \sum_{r=1}^{k+1} r^{3} &= \sum_{r=1}^{k} r^{3} + (k+1)^{3} \\ &= \frac{1}{4}k^{2}(k+1)^{2} + (k+1)^{3} \\ &= \frac{1}{4}(k+1)^{2}\left( k^{2}+4(k+1)\right) \\ &= \frac{1}{4}(k+1)^{2}\left(k^{2} +4k+4 \right) \\ &= \frac{1}{4}(k+1)^{2}(k+2)^{2} \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

## Divisibility

Q) Prove that $3^{2n}-1$ is divisible by 8 for all natural numbers $n$.

A) First show that the formula holds for $n=1$ $$3^{2}-1 = 8$$ Which is obviously divisible by 8. Suppose the formula holds for some $n=k$ $$f(k) = 3^{2k}-1 \textrm{ is divisible by 8}$$ Then let $n=k+1$ and subtract $f(k)$ \begin{align} f(k+1)-f(k) &= 3^{2(k+1)} - 1 - (3^{2k}-1) \\ &= 3^{2(k+1)}- 3^{2k} \\ &= 3^{2}3^{2k} - 3^{2k} \\ &= (9-1)3^{2k} \\ &= 8(3^{2k}) \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

Q) Prove that $n^{2}-3n$ is divisible by 2 for all natural numbers $n$.

A) First show that the formula holds for $n=1$ $$1^{2}-3 = -2 = 2(-1)$$ Suppose the formula holds for some $n=k$ $$f(k) = k^{2}-3k \textrm{ is divisible by 2}$$ Then let $n=k+1$ and subtract $f(k)$ \begin{align} f(k+1)-f(k) &= (k+1)^{2}-3(k+1)-k^{2}+3k \\ &= k^{2}+2k+1-3k-3-k^{2}+3k \\ &= 2k+1-3 \\ &= 2(k-1) \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

### Recurrence relations

Q) With $u_{1}=6$ and $u_{n+1}=u_{n}+2^{n}+4$, prove that $u_{n}=2^{n}+4n$ for all natural numbers $n$.

A) First show that the formula holds for $n=1$ $$u_{1} = 2^{1}+4 = 6$$ Suppose the formula holds for some $n=k$ $$u_{k}=2^{k}+4k$$ Then going back to the formula for $u_{n+1}$ in the question \begin{align} u_{k+1}&=u_{k}+2^{k}+4 \\ &= 2^{k}+4k + 2^{k}+4 \\ &= 2(2^{k}) + 4(k+1) \\ &= 2^{k+1} +4(k+1) \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

### Matrices

Q) Let $\mathbf{A} = \left( \begin{array}{cc} 1 & 0 \\ 5 & 1 \end{array}\right)$. Show that $\mathbf{A}^{n} = \left(\begin{array}{cc} 1 & 0 \\ 5n & 1 \end{array}\right)$ for all natural numbers $n$.

A) First show that the formula holds for $n=1$ $$\mathbf{A}^{1} = \left(\begin{array}{cc} 1 & 0 \\ 5 & 1 \end{array}\right)$$ Suppose the formula holds for some $n=k$ $$\mathbf{A}^{k} = \left(\begin{array}{cc} 1 & 0 \\ 5k & 1 \end{array}\right)$$ Now $\mathbf{A}^{k+1} = \mathbf{A}^{k}\mathbf{A}$, so \begin{align} \mathbf{A}^{k+1} &= \left(\begin{array}{cc} 1 & 0 \\ 5k & 1 \end{array}\right)\left(\begin{array}{cc} 1 & 0 \\ 5 & 1 \end{array}\right) \\ &= \left(\begin{array}{cc} 1 & 0 \\ 5k+5 & 1 \end{array}\right) \\ &= \left(\begin{array}{cc} 1 & 0 \\ 5(k+1) & 1 \end{array}\right) \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.

Q) (Hard) Let $\mathbf{A} = \left( \begin{array}{cc} -1 & 0 \\ 2 & 1 \end{array}\right)$. Show that $\mathbf{A}^{n} = \left(\begin{array}{cc} (-1)^{n} & 0 \\ 1-(-1)^{n} & 1 \end{array}\right)$ for all natural numbers $n$.

A) First show that the formula holds for $n=1$ $$\mathbf{A}^{1} = \left(\begin{array}{cc} -1 & 0 \\ 1-(-1) & 1 \end{array}\right) = \left( \begin{array}{cc} -1 & 0 \\ 2 & 1 \end{array}\right)$$ Suppose the formula holds for some $n=k$ $$\mathbf{A}^{k} = \left(\begin{array}{cc} (-1)^{k} & 0 \\ 1-(-1)^{k} & 1 \end{array}\right)$$ Now $\mathbf{A}^{k+1} = \mathbf{A}^{k}\mathbf{A}$, so \begin{align} \mathbf{A}^{k+1} &= \left(\begin{array}{cc} (-1)^{k} & 0 \\ 1-(-1)^{k} & 1 \end{array}\right)\left( \begin{array}{cc} -1 & 0 \\ 2 & 1 \end{array}\right) \\ &= \left(\begin{array}{cc} -(-1)^{k} & 0 \\ (-1)^{k}-1+2 & 1 \end{array}\right) \\ &= \left(\begin{array}{cc} (-1)^{k+1} & 0 \\ 1+(-1)^{k} & 1 \end{array}\right) \\ &= \left(\begin{array}{cc} (-1)^{k+1} & 0 \\ 1+(-1)(-1)^{k+1} & 1 \end{array}\right) \textrm{ since } (-1)^{k-1}=(-1)^{k+1} \\ &= \left(\begin{array}{cc} (-1)^{k+1} & 0 \\ 1-(-1)^{k+1} & 1 \end{array}\right) \end{align} So we have shown that if it is true for some $n=k$ it is also true for $n=k+1$. We have shown that it is true for $n=1$, therefore by the principle of mathematical induction it is true for all the natural numbers $n$. $\blacksquare$.