Proof by induction: matrices

Structure

To prove Mⁿ = A(n):

• Basis: A(1) = M.
• Assume M^k = A(k).
• Step: M^k+1 = M^k M = A(k) M. Multiply out and simplify to A(k + 1). (MM^k also works, because powers of the same matrix commute.)
• Conclusion.

Example

Prove (3 -4; 1 -1)ⁿ = (2n + 1 -4n; n 1 - 2n).

n = 1: (3 -4; 1 -1). True.

Assume M^k = (2k + 1 -4k; k 1 - 2k). Then

M^k+1 = (2k + 1 -4k; k 1 - 2k)(3 -4; 1 -1)

= (6k + 3 - 4k, -8k - 4 + 4k; 3k + 1 - 2k, -4k - 1 + 2k)

= (2k + 3 -4k - 4; k + 1 -2k - 1) = (2(k + 1) + 1 -4(k + 1); k + 1 1 - 2(k + 1)).

That is the formula with n = k + 1.

Tips

Multiply carefully entry by entry and set out the four entries clearly. Finish by writing each entry in terms of (k + 1), so the examiner can see it matches.

Worked example

Prove by induction that (1 2; 0 1)ⁿ = (1 2n; 0 1).

1. n = 1: (1 2; 0 1). True.
2. Assume (1 2; 0 1)^k = (1 2k; 0 1).
3. (1 2k; 0 1)(1 2; 0 1) = (1 2 + 2k; 0 1) = (1 2(k + 1); 0 1).
4. True for n = 1, and true for k implies true for k + 1, so true for all positive integers n.

Answer: Proved

Check yourself

1. M = (3 -4; 1 -1) and Mⁿ = (2n + 1 -4n; n 1 - 2n). Find the top-right entry of M⁵.
   Show answer

   -20. -4n with n = 5 gives -20.

2. M = (3 -4; 1 -1). Calculate M² directly and give its top-left entry.
   Show answer

   5. Row 1 times column 1: 3×3 + (-4)×1 = 5, which agrees with 2n + 1 = 5.

3. (1 2; 0 1)ⁿ = (1 2n; 0 1). Find the top-right entry of (1 2; 0 1)¹⁰.
   Show answer

   20. 2n = 20.

4. (2 1; 0 1)ⁿ = (2ⁿ 2ⁿ - 1; 0 1). Find the top-right entry of (2 1; 0 1)⁶.
   Show answer

   63. 2⁶ - 1 = 63.

5. In the inductive step for Mⁿ, which product gives M^k+1?
   • M^k + M
   • M^k M
   • M^k × k
   • (M^k)²
   Show answer

   M^k M. M^k+1 = M^k × M (or M × M^k).

6. In the step for (2 1; 0 1)ⁿ, you compute (2^k 2^k - 1; 0 1)(2 1; 0 1). What is the top-right entry?
   • 2^k - 1
   • 2^k+1
   • 2^k × (2^k - 1)
   • 2^k + 2^k - 1 = 2^k+1 - 1
   Show answer

   2^k + 2^k - 1 = 2^k+1 - 1. Row 1 times column 2: 2^k × 1 + (2^k - 1) × 1 = 2 × 2^k - 1 = 2^k+1 - 1.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics, Further Mathematics and Pure Mathematics specification (issue 3), Unit FP1
• Pearson Edexcel IAL Further Pure Mathematics 1 scheme of work

Last updated 8 November 2026. Spotted a mistake? Tell us.