Proof by Induction (AQA A-Level Further Maths): Revision Notes

Worked Example: Proving a Geometric Series Formula

Prove by induction that $\displaystyle\sum_{r=1}^{n} 4^{r-1} = \frac{1}{3}(4^n - 1)$ for all $n \in \mathbb{N}$

Step 1: Base case (when $n = 1$)

Calculate the left-hand side (LHS): $\sum_{r=1}^{1} 4^{r-1} = 4^0 = 1$

Calculate the right-hand side (RHS): $\frac{1}{3}(4^1 - 1) = \frac{1}{3}(3) = 1$

Since LHS = RHS, the statement is true for $n = 1$.

Step 2: Inductive step

Assume the statement is true for $n = k$. This means: $\sum_{r=1}^{k} 4^{r-1} = \frac{1}{3}(4^k - 1)$

Now consider $n = k + 1$. We need to prove: $\sum_{r=1}^{k+1} 4^{r-1} = \frac{1}{3}(4^{k+1} - 1)$

Write the sum to the $(k+1)$th term as a sum to the $k$th term plus the $(k+1)$th term: $\sum_{r=1}^{k+1} 4^{r-1} = \sum_{r=1}^{k} 4^{r-1} + 4^{k+1-1}$

Since we are assuming the statement is true for $n = k$, we can replace $\sum_{r=1}^{k} 4^{r-1}$ with $\frac{1}{3}(4^k - 1)$: $= \frac{1}{3}(4^k - 1) + 4^k$

Collect like terms and use index laws: $= \frac{1}{3}(4^k - 1 + 3 \times 4^k)$ $= \frac{1}{3}(4 \times 4^k - 1)$ $= \frac{1}{3}(4^{k+1} - 1)$

This is $\frac{1}{3}(4^n - 1)$ with $n$ replaced by $k + 1$.

So the statement is true when $n = k + 1$.

Step 3: Conclusion

The statement is true for $n = 1$ and by assuming it is true for $n = k$ it is shown to be true for $n = k + 1$.

Therefore, by mathematical induction, it is true for all $n \in \mathbb{N}$.

Worked Example: Proving the Sum of Squares Formula

Prove by induction that $\displaystyle\sum_{r=1}^{n} r^2 = \frac{1}{6}n(n+1)(2n+1)$ for all $n \in \mathbb{N}$

Step 1: Base case (when $n = 1$)

Calculate LHS: $\sum_{r=1}^{1} r^2 = 1^2 = 1$

Calculate RHS: $\frac{1}{6} \times 1 \times (1+1) \times (2 \times 1 + 1) = \frac{1}{6} \times 1 \times 2 \times 3 = 1$

Since LHS = RHS, the statement is true for $n = 1$.

Step 2: Inductive step

Assume the statement is true for $n = k$:

$\sum_{r=1}^{k} r^2 = \frac{1}{6}k(k+1)(2k+1)$

Consider $n = k + 1$ and substitute into the formula:

$\sum_{r=1}^{k+1} r^2 = \sum_{r=1}^{k} r^2 + (k+1)^2$

Using the inductive hypothesis:

$= \frac{1}{6}k(k+1)(2k+1) + (k+1)^2$

Factorise by taking out the common factor $(k+1)$:

$= \frac{1}{6}(k+1)[k(2k+1) + 6(k+1)]$

$= \frac{1}{6}(k+1)[2k^2 + k + 6k + 6]$

$= \frac{1}{6}(k+1)[2k^2 + 7k + 6]$

Look for common factors - avoid multiplying out brackets unless necessary:

$= \frac{1}{6}(k+1)(k+2)(2k+3)$

$= \frac{1}{6}(k+1)[(k+1)+1][2(k+1)+1]$

This is $\frac{1}{6}n(n+1)(2n+1)$ with $n$ replaced by $k+1$.

So the statement is true when $n = k + 1$.

Step 3: Conclusion

The statement is true for $n = 1$ and by assuming it is true for $n = k$ it is shown to be true for $n = k + 1$.

Therefore, by mathematical induction, it is true for all $n \in \mathbb{N}$.

Worked Example: Divisibility by 3

Prove that $n^3 + 2n$ is divisible by 3 for all $n \in \mathbb{N}$

Step 1: Base case (when $n = 1$)

Calculate the value of the expression: $n^3 + 2n = 1^3 + 2(1) = 1 + 2 = 3$

Since $3 = 3 \times 1$, this is divisible by 3.

So the statement is true when $n = 1$.

Step 2: Inductive step

Assume the statement is true for $n = k$. This means $k^3 + 2k$ is divisible by 3.

Consider $n = k + 1$ and substitute into the expression:

$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2$

$= k^3 + 3k^2 + 5k + 3$

Rearrange to separate the part we know is divisible by 3:

$= (k^3 + 2k) + (3k^2 + 3k + 3)$

Since $k^3 + 2k$ is divisible by 3 (by our assumption), we can write it as $3A$ for some integer $A$:

$= 3A + 3(k^2 + k + 1)$

$= 3(A + k^2 + k + 1)$

This is divisible by 3.

Step 3: Conclusion

The statement is true for $n = 1$ and by assuming it is true for $n = k$ it is shown to be true for $n = k + 1$.

Therefore, by mathematical induction, it is true for all $n \in \mathbb{N}$.

Worked Example: Proving a Multiple of 7

Given that $f(n) = 2^{n+1} + 3^{2n-1}$, prove by induction that $f(n)$ is a multiple of 7 for all positive integers $n$

Step 1: Base case (when $n = 1$)

Calculate the value of the expression:

$f(1) = 2^{1+1} + 3^{2(1)-1} = 2^2 + 3^1 = 4 + 3 = 7$

Since $7 = 7 \times 1$, this is a multiple of 7.

Step 2: Inductive step

Assume $f(k)$ is a multiple of 7. Consider $f(k+1)$:

$f(k+1) = 2^{(k+1)+1} + 3^{2(k+1)-1}$

$= 2^{k+2} + 3^{2k+1}$

Use index laws to write in terms of $2^{k+1}$ and $3^{2k-1}$:

$= 2^{k+1} \cdot 2^1 + 3^{2k-1} \cdot 3^2$

$= 2(2^{k+1}) + 9(3^{2k-1})$

Rearrange to separate out terms containing $f(k)$:

$= 2(2^{k+1} + 3^{2k-1}) + 7(3^{2k-1})$

$= 2f(k) + 7(3^{2k-1})$

Since $f(k)$ is a multiple of 7 (by assumption) and $7(3^{2k-1})$ is clearly a multiple of 7, their sum is also a multiple of 7.

Step 3: Conclusion

$f(1)$ is a multiple of 7 and by assuming that $f(k)$ is a multiple of 7, it is shown that $f(k+1)$ is a multiple of 7.

Therefore, by mathematical induction, $f(n)$ is a multiple of 7 for all positive integers $n$.