9.1.2 Common Cases of Proof by Induction

Mathematical induction is often used to prove three main types of problems:

Summation of Series
Divisibility
Matrix Products This note explains each type, along with worked examples, to demonstrate how induction applies in each case.

Summation of Series

infoNote

Worked Example

Prove by induction that:

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

Step 1: Base Case ( $n = 1$ )

For $n = 1$

\sum_{r=1}^1 r^2 = 1^2 = 1, \quad \text{and} \quad \frac{1(1+1)(2 \cdot 1 + 1)}{6} = 1

Thus, the formula holds for $n=1$

Step 2: Inductive Hypothesis

Assume the formula holds for $n=k$

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

Step 3: Inductive Step ( $n = k+1$ )

We need to prove the formula holds for $n=k+1$

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

Using the inductive hypothesis:

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

Factorise $(k+1)$

\sum_{r=1}^{k+1} r^2 = \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6}

Simplify:

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

Factorise the quadratic:

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

Thus, the formula holds for $n=k+1$

Conclusion

By induction, the formula:

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

is true for all $n \geq 1$

Divisibility

infoNote

Worked Example

Prove by induction that $n^3 + 2n$ is divisible by $3$ for all $n \geq 1$

Step 1: Base Case ( $n = 1$ )

For $n = 1$

1^3 + 2 \times 1 = 3

which is divisible by 3

Step 2: Inductive Hypothesis

Assume $n^3 + 2n$ is divisible by $3$ for $n = k$

k^3 + 2k = 3m \quad \text{for some integer } m

Step 3: Inductive Step ( $n = k+1$ )

We need to prove $(k+1)^3 + 2(k+1)$ is divisible by $3$ .

Expand $(k+1)^3$

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

Substitute into the expression:

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

Simplify:

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

From the inductive hypothesis, $k^3 + 2k = 3m$

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

Factor out $3$ :

(k+1)^3 + 2(k+1) = 3\big(m + k^2 + k + 1\big)

Thus, $(k+1)^3 + 2(k+1)$ is divisible by 3.

Conclusion

By induction, $n^3 + 2n$ is divisible by 3 for all $n \geq 1$

Matrix Products

infoNote

Worked Example

Prove by induction that:

\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^n = \begin{pmatrix} 2^n + 1 & 2^{n+1} - 2 \\ 2^{n-1} & 2^n - 1 \end{pmatrix}

Step 1: Base Case ( $n = 1$ )

For $n = 1$

\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^1 = \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}

The given formula for $n = 1$

\begin{pmatrix} 2^1 + 1 & 2^2 - 2 \\ 2^0 & 2^1 - 1 \end{pmatrix} = \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}

Thus, the formula holds for $n = 1$

Step 2: Inductive Hypothesis

Assume the formula holds for $n = k$

\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^k = \begin{pmatrix} 2^k + 1 & 2^{k+1} - 2 \\ 2^{k-1} & 2^k - 1 \end{pmatrix}

Step 3: Inductive Step ( $n = k+1$ )

We need to prove:

\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^{k+1} = \begin{pmatrix} 2^{k+1} + 1 & 2^{k+2} - 2 \\ 2^k & 2^{k+1} - 1 \end{pmatrix}

Multiply $\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^k$ by $\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}$ :

\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^{k+1} = \begin{pmatrix} 2^k + 1 & 2^{k+1} - 2 \\ 2^{k-1} & 2^k - 1 \end{pmatrix} \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}

Perform matrix multiplication:

\begin{pmatrix} (3)(2^k+1) + (4)(2^{k-1}) & (4)(2^{k+1}-2) + (4)(2^k - 1) \\ ... \end{pmatrix}

(Simplify using arithmetic rules for $2^k$ .)

Note Summary

infoNote

Common Mistakes

Failing to clearly define the inductive hypothesis. Always state what you are assuming to be true.
Errors in simplifying algebraic expressions. Take care with powers and coefficients.
Misapplying initial conditions**.** Verify that the base case aligns with the problem statement.
Incorrect matrix multiplications. Be methodical when calculating matrix entries.

infoNote

Key Formulas

Summation of Series:

\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}.

Divisibility: To prove ( $f(n)$ ) is divisible by $k$ , show:

f(k+1) = f(k) + \text{some multiple of } k

Matrix Products: Use the inductive formula for powers of a matrix and verify consistency.

Common Cases of Proof by Induction Simplified Revision Notes for A-Level Edexcel Further Maths Core Pure

9.1.2 Common Cases of Proof by Induction

Summation of Series

Worked Example

Divisibility

Worked Example

Matrix Products

Worked Example

Note Summary

Common Mistakes

Key Formulas

500K+ Students Use These Powerful Tools to Master Common Cases of Proof by Induction For their A-Level Exams.

Other Revision Notes related to Common Cases of Proof by Induction you should explore