Practise › Questions › Induction: divisibility and matrices

Induction: divisibility and matrices questions

The same induction argument applied to two further kinds of statement. Expressions that stay divisible by a fixed number, and matrix powers that follow a pattern.

7 original questions · 30 marks · the induction: divisibility and matrices notes · Further proof

Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.

• 2 marks · warm-up

  Let f(n) = 8ⁿ − 1. Show that f(1) is divisible by 7, and write down the inductive hypothesis for the claim that 7 divides f(n) for all positive integers n.

  Worked answer

  f(1) = 8 − 1 = 7, which is divisible by 7. Hypothesis: assume f(k) = 8^k − 1 is divisible by 7 for some positive integer k. B1 for the base case, B1 for the hypothesis.

• 3 marks · warm-up

  Using f(n) = 8ⁿ − 1, simplify f(k + 1) − 8f(k) and hence complete the divisibility proof.

  Worked answer

  f(k + 1) − 8f(k) = (8^k+1 − 1) − (8^k+1 − 8) = 7. So f(k + 1) = 8f(k) + 7, a multiple of 7 plus 7, and so divisible by 7. With the base case, 7 divides 8ⁿ − 1 for all n. M1 for forming f(k + 1) − 8f(k), A1 for the constant remainder, A1 for the conclusion.

• 5 marks · prove

  Prove by induction that 3²ⁿ + 7 is divisible by 8 for all positive integers n.

  Worked answer

  Base: 3² + 7 = 16 = 8 × 2. Step: with f(k) = 3^2k + 7 assumed divisible by 8, f(k + 1) = 9 × 3^2k + 7 = 9f(k) − 56. Both terms are multiples of 8 (56 = 8 × 7), so f(k + 1) is too. B1 for the base case, M1 for writing f(k + 1) in terms of f(k), A1 for 9f(k) − 56, A1 for both terms being multiples of 8, A1 for the conclusion. The multiplier 9 comes from 3^2(k+1) = 9 × 3^2k: each step multiplies the power part by 9.

• 5 marks

  Let M be the matrix with rows (1, 1) and (0, 1). Prove by induction that Mⁿ has rows (1, n) and (0, 1).

  Worked answer

  Base: M¹ has rows (1, 1), (0, 1), matching n = 1. Step: assume M^k has rows (1, k), (0, 1). Then M^k+1 = M^kM multiplies to rows (1, k + 1), (0, 1), since the top-right entry is 1 × 1 + k × 1 = k + 1 and the rest are unchanged. So the pattern holds for all n. B1 for the base case, M1 for writing M^k+1 = M^kM, A1 for the top-right entry, A1 for the required form, A1 for the conclusion. The shear just accumulates its slide.

• 5 marks

  Let D be the matrix with rows (2, 0) and (0, 3). Prove by induction that Dⁿ has rows (2ⁿ, 0) and (0, 3ⁿ).

  Worked answer

  Base: D¹ has rows (2, 0), (0, 3) = (2¹, 0), (0, 3¹). Step: assume the result at k; multiplying by D scales the top-left entry by 2 and the bottom-right by 3, giving 2^k+1 and 3^k+1 with the zeros preserved. B1 for the base case, M1 for multiplying by D, A1 for the top-left entry, A1 for the bottom-right entry, A1 for the conclusion. Diagonal matrices power entry by entry, and induction is how that sentence is earned.

• 3 marks

  In divisibility proofs the working often forms f(k + 1) − m f(k) for a chosen multiplier m. Explain how m is chosen, and why the manoeuvre works.

  Worked answer

  Choose m to match the growth of the power term, so the powers cancel. For 8ⁿ − 1 take m = 8, for 3²ⁿ + 7 take m = 9. What remains is a constant, and if that constant is divisible by the target then f(k + 1) = m f(k) + constant inherits divisibility from the hypothesis. B1 for choosing m to match the growth of the power term, B1 for the powers cancelling to leave a constant, B1 for that constant carrying the divisibility.

• 7 marks · stretch

  M is the matrix with rows (3, −4) and (1, −1). Prove by induction that Mⁿ has rows (1 + 2n, −4n) and (n, 1 − 2n) for all positive integers n.

  Worked answer

  Base: at n = 1 the formula gives rows (3, −4) and (1, −1), which is M. Step: assume M^k has rows (1 + 2k, −4k) and (k, 1 − 2k). Then M^k+1 = M^kM, and the four entries are 3(1 + 2k) − 4k = 3 + 2k, −4(1 + 2k) + 4k = −4 − 4k, 3k + (1 − 2k) = k + 1 and −4k − (1 − 2k) = −1 − 2k. Rewriting, 3 + 2k = 1 + 2(k + 1), −4 − 4k = −4(k + 1) and −1 − 2k = 1 − 2(k + 1), so the rows are (1 + 2(k + 1), −4(k + 1)) and (k + 1, 1 − 2(k + 1)), the formula at n = k + 1. True at n = 1 and inherited at every step, so true for all positive integers n. B1 for the base case, M1 for forming M^kM, M1 for at least one correct entry, A1 A1 for all four entries, A1 for rewriting them in terms of k + 1, A1 for the conclusion. Write M^k+1 as M^kM rather than MM^k and the hypothesis sits ready on the left; either order works here, but matrices do not commute in general, so the product is worth writing down explicitly rather than assuming.

The same practice on paper: the printable workbook for this topic, questions and a worked answer book.

Practise induction: divisibility and matrices one question at a time

The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.