Maths › Further proof › Induction: divisibility and matrices

Induction: divisibility and matrices

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.

Year FMEDEXCEL 9FM0 CP1 1.1

Builds on Proof by induction: sums and series.

IN THIS TOPIC

  • Prove divisibility statements by induction using the subtract-a-multiple rearrangement.
  • Prove a formula for the nth power of a matrix by induction, shown entry by entry.

COMMON MISCONCEPTION

The inductive step does all the work; the base case is a formality that can be skipped.

Divisibility by induction

A claim like '8n − 1 is divisible by 7 for all positive integers n' fits induction as soon as it is written usefully. The base case is a number check, 8 − 1 = 7. The step must turn information about 8k − 1 into information about 8k+1 − 1, and the standard move is to write the new expression as a multiple of the old one plus a visible multiple of 7.

The first three values of 8 to the n minus 1, each dividing cleanly by 78¹ − 1 = 7= 7 × 18² − 1 = 63= 7 × 98³ − 1 = 511= 7 × 73the factor of 7 survives every step up in n
FIG. 17, 63 and 511: each of the first values of 8ⁿ − 1 is openly 7 times an integer, and induction extends the pattern for ever.

WORKED EXAMPLE

8 to the n, minus one

Prove by induction that 8n − 1 is divisible by 7 for all positive integers n.

Base case, n = 1. 8 − 1 = 7, divisible by 7. True.

Assume 8k − 1 = 7m for some integer m.

Then 8k+1 − 1 = 8 × 8k − 1 = 8(8k − 1) + 7 = 8 × 7m + 7 = 7(8m + 1), a multiple of 7.

True for n = 1 and inherited from k to k + 1, so true for all positive integers n by induction. ∎

Practise the rearrangement 8 × 8k − 1 = 8(8k − 1) + 7 until it is automatic. Pull out a multiple of the assumed expression, and whatever is left over has to be checked divisible on its own. Writing the hypothesis as 7m with m an integer keeps the final factorisation valid, and it turns the last line into something an examiner can tick without squinting.

Matrix powers by induction

When a matrix power follows a visible pattern, induction turns the pattern into a theorem. The step is one matrix multiplication. Assume the formula for Ak, multiply by A once more, and confirm the entries land where the formula for k + 1 says they should.

Powers of a shear matrix: the top-right entry counts the power, exactly as the induction claims1101A1201A²1301A³top-right entry: 1, 2, 3, … , n
FIG. 2A shear matrix raised to the first, second and third power: only the top-right entry moves, counting 1, 2, 3.

GUIDED PRACTICE

A shear, raised to the n

A is the matrix with rows (1, 1) and (0, 1). Prove by induction that An has rows (1, n) and (0, 1) for all positive integers n.

Show the working

Base case, n = 1. The claimed matrix with n = 1 is A itself. True.

Assume Ak has rows (1, k) and (0, 1). Then Ak+1 = AkA, and multiplying gives top row (1 × 1 + k × 0, 1 × 1 + k × 1) = (1, k + 1), bottom row (0, 1).

That is the formula at n = k + 1, so by induction it holds for every positive integer n. ∎ Show the multiplication entry by entry. Asserting the product is where these proofs lose their method mark.

Why the base case is not decoration

Without a base case the argument proves nothing, since 'each domino topples the next' is useless if no domino ever falls. Try it on the false statement '4n + 1 is divisible by 3'. The inductive step goes through happily, because 4k+1 + 1 = 4(4k + 1) − 3, yet 4 + 1 = 5 sinks it at n = 1 and the claim is false for every n. A statement can inherit perfectly and still be wrong throughout.

ASSESSMENT FOCUS

  • Introduce the hypothesis with a letter. 'Assume 8k − 1 = 7m for an integer m' makes the final factorisation checkable.
  • For divisibility, rearrange the k + 1 expression around the assumed one before touching anything else.
  • For matrix proofs, multiply the assumed power by A and show all four entries of the product.
  • The conclusion sentence is the same in every flavour. Base case, inheritance, 'by induction'.
  • If the final bracket is not obviously a multiple, factor out the divisor explicitly and say so.

CHECK YOURSELF

Prove by induction that 9n + 11 is divisible by 4 for all positive integers n.

Show a hint

Write 9k+1 + 11 as 9(9k + 11) minus a constant, and check the constant.

Show the answer

Base case, n = 1. 9 + 11 = 20 = 4 × 5, true. Assume 9k + 11 = 4m for an integer m. Then 9k+1 + 11 = 9(9k + 11) − 88 = 9 × 4m − 88 = 4(9m − 22), a multiple of 4. True for n = 1 and inherited from k to k + 1, so true for all positive integers n by induction.

Divisibility steps rewrite the k + 1 case as (multiple of the k case) + (visible multiple).

Matrix steps are one multiplication, A to the k times A, worked entry by entry.

WORKBOOK

Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.

Question workbook

PDF · 32 KB · print edition · white background

Question workbook

PDF · 32 KB · screen edition · navy

Answer book

PDF · 37 KB · fully worked · navy
7 questions on this topicAnswer them one at a time and mark yourself against the worked answer.Practise this topic

Or read them with their worked answers on the induction: divisibility and matrices questions page.

CHECK YOUR PROGRESS

Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.

  • Prove divisibility statements by induction using the subtract-a-multiple rearrangement.
  • Prove a formula for the nth power of a matrix by induction, shown entry by entry.

Open the full revision checklist to see every objective in the course in one place.