Proof by Induction (Edexcel A-Level Further Mathematics): Revision Notes

📚 Revision Notes
Revision NotesModel AnswersQuizzesFlashcards

9.1.2 Common Cases of Proof by Induction

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

  1. Summation of Series
  2. Divisibility
  3. 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:

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

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

For n=1n = 1

∑r=11r2=12=1,and1(1+1)(2⋅1+1)6=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 n=1

Step 2: Inductive Hypothesis

Assume the formula holds for n=kn=k

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

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

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

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

Using the inductive hypothesis:

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

Factorise (k+1)(k+1)

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

Simplify:

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

Factorise the quadratic:

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

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

Conclusion

By induction, the formula:

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

is true for all n≥1n \geq 1

Divisibility

infoNote

Worked Example

Prove by induction that n3+2nn^3 + 2n is divisible by 33 for all n≥1n \geq 1

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

For n=1n = 1

13+2×1=31^3 + 2 \times 1 = 3

which is divisible by 3

Step 2: Inductive Hypothesis

Assume n3+2nn^3 + 2n is divisible by 33 for n=kn = k

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

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

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

Expand (k+1)3(k+1)^3

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

Substitute into the expression:

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

Simplify:

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

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

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

Factor out 33:

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

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

Conclusion

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

Matrix Products

infoNote

Worked Example

Prove by induction that:

(3412)n=(2n+12n+1−22n−12n−1)\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=1n = 1)

For n=1n = 1

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

The given formula for n=1n = 1

(21+122−22021−1)=(3412)\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=1n = 1

Step 2: Inductive Hypothesis

Assume the formula holds for n=kn = k

(3412)k=(2k+12k+1−22k−12k−1)\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+1n = k+1)

We need to prove:

(3412)k+1=(2k+1+12k+2−22k2k+1−1)\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 (3412)k\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}^k by (3412)\begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix}:

(3412)k+1=(2k+12k+1−22k−12k−1)(3412)\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:

((3)(2k+1)+(4)(2k−1)(4)(2k+1−2)+(4)(2k−1)...)\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 2k2^k.)

Note Summary

infoNote

Common Mistakes

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

Key Formulas

  1. Summation of Series:
∑r=1nr2=n(n+1)(2n+1)6.\sum_{r=1}^n r^2 = \frac{n(n+1)(2n+1)}{6}.
  1. Divisibility: To prove (f(n)f(n)) is divisible by kk, show:
f(k+1)=f(k)+some multiple of kf(k+1) = f(k) + \text{some multiple of } k
  1. Matrix Products: Use the inductive formula for powers of a matrix and verify consistency.

Explore Edexcel A-Level Further Mathematics Model Answers by Topics

Proof by Induction

Explore Edexcel A-Level Further Mathematics Quizzes by Topics

Proof by Induction

Explore Edexcel A-Level Further Mathematics Flashcards by Topics

Proof by Induction

Join 100,000+ A-Level students studying Revision Notes with us.

Select your subjects, and get access to A+ resources today.