Maths › Further proof › Induction: divisibility and matrices

Induction: divisibility and matrices

The induction argument extends to three further kinds of statement: expressions divisible by a fixed number, formulae for matrix powers, and inequalities. The structure of the proof is unchanged; the algebra in the inductive step differs, and an inequality is proved by chaining a second inequality onto the assumed one rather than by rearrangement.

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.
Prove an inequality by induction, chaining a second inequality onto the assumed one.
Find the value of n from which an inequality holds, and put the base case there.

COMMON MISCONCEPTION

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

The step passes a property from k to k + 1; the base case is what gives it a true value to start from. Take the false claim that 4ⁿ + 1 is divisible by 3: the step goes through, since 4^k+1 + 1 = 4(4^k + 1) − 3, yet 4 + 1 = 5 is not a multiple of 3 and the claim fails for every n. Put the base case at the first value of the stated range.

Divisibility by induction

In a divisibility proof, rewrite f(k + 1) so that the inductive hypothesis supplies one divisible part and the remaining terms contain the required divisor explicitly. For '8ⁿ − 1 is divisible by 7 for all positive integers n', the base case is the calculation 8 − 1 = 7, and the step writes 8^k+1 − 1 as a multiple of 8^k − 1 plus an explicit multiple of 7.

Three boxes holding seven, sixty-three and five hundred and eleven, each rewritten as seven times a whole number: the divisibility that induction proves persists for every power. — FIG. 17, 63 and 511: each of the first values of 8ⁿ − 1 is 7 times an integer, and induction establishes the pattern for every n.

WORKED EXAMPLE

8 to the n, minus one

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

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

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

Then 8^k+1 − 1 = 8 × 8^k − 1 = 8(8^k − 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. ∎

The rearrangement 8 × 8^k − 1 = 8(8^k − 1) + 7 is the general pattern: extract a multiple of the assumed expression, then show that the remaining terms are divisible by the same divisor. Write the hypothesis as 7m with m an integer so that the final expression can be factorised as an explicit multiple of 7.

Matrix powers by induction

For a matrix identity, multiply the assumed expression for M^k by M in the correct order and simplify to the formula for M^k+1. The inductive step is a single matrix multiplication.

Three two-by-two grids for a shear matrix and its square and cube: every entry fixed except the top-right, which climbs one, two, three, the pattern the induction proof locks in for all n. — FIG. 2A shear matrix raised to the first, second and third power: only the top-right entry changes, taking the values 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 Aⁿ 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 A^k has rows (1, k) and (0, 1). Then A^k+1 = A^kA, 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 rather than stating the product.

Inequalities by induction

For an inequality the inductive step chains two inequalities rather than rearranging an identity: start from the assumed inequality, then supply a second inequality that reaches the target. Work from the k + 1 expression towards the k one so that the assumption can be applied, and state the second inequality explicitly before using it.

An inequality of this kind often holds only from some value of n onwards, so place the base case at the first value of the stated range rather than at n = 1.

WORKED EXAMPLE

2 to the n against n squared

Prove that 2ⁿ > n² for all integers n ≥ 5.

Base case, n = 5. 2⁵ = 32 and 5² = 25, and 32 > 25. True.

Assume 2^k > k² for some integer k ≥ 5.

Then 2^k+1 = 2 × 2^k > 2k², using the assumption.

Second inequality: 2k² − (k + 1)² = k² − 2k − 1 = (k − 1)² − 2, which is positive for k ≥ 5, so 2k² > (k + 1)².

Chaining the two, 2^k+1 > 2k² > (k + 1)², the statement at n = k + 1. True at n = 5 and inherited from k to k + 1, so 2ⁿ > n² for all integers n ≥ 5 by induction. ∎

The starting value matters here. The statement holds at n = 1, fails at n = 2, 3 and 4, where 2ⁿ is 4, 8 and 16 against 4, 9 and 16, and holds again from n = 5 onwards. A base case at n = 1 would establish nothing about n = 5, because the implication from k to k + 1 does not hold across that range. State the range in the conclusion sentence as well as in the base case.

GUIDED PRACTICE

Three to the n against n cubed

Prove that 3ⁿ > n³ for all integers n ≥ 4.

Show the working

Base case, n = 4. 3⁴ = 81 and 4³ = 64, and 81 > 64. True.

Assume 3^k > k³ for some integer k ≥ 4. Then 3^k+1 = 3 × 3^k > 3k³.

The second inequality is 3k³ > (k + 1)³, which rearranges to 3 > (1 + 1/k)³. For k ≥ 4, (1 + 1/k)³ ≤ (5/4)³ = 125/64 < 3, so 3k³ > (k + 1)³.

So 3^k+1 > 3k³ > (k + 1)³. True at n = 4 and inherited from k to k + 1, so the result holds for all integers n ≥ 4 by induction. ∎ State the second inequality on its own line before joining the chain.

Why the base case is required

Without a base case the inductive step establishes nothing, because the implication from k to k + 1 has no true starting value to propagate. Consider the false statement '4ⁿ + 1 is divisible by 3'. The inductive step is valid, since 4^k+1 + 1 = 4(4^k + 1) − 3, but 4 + 1 = 5 is not divisible by 3, and the claim is false for every n.

ASSESSMENT FOCUS

Introduce the hypothesis with a letter. 'Assume 8^k − 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 each case: base case, the implication from k to k + 1, and 'by induction'.
If the final bracket is not obviously a multiple, factor out the divisor explicitly and say so.
For an inequality, use the assumption first, then state a second inequality explicitly, and finish by joining the two into one chain.
Identify where the stated range begins. Put the base case at the first value of that range and state that value again in the conclusion.

CHECK YOURSELF

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

Show a hint

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

Show the answer

Base case, n = 1. 9 + 11 = 20 = 4 × 5, true. Assume 9^k + 11 = 4m for an integer m. Then 9^k+1 + 11 = 9(9^k + 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.

Inequality steps chain: assumption first, then a second inequality you state, and the base case sits where the range starts.

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.

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

USED LATER IN

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.
Prove an inequality by induction, chaining a second inequality onto the assumed one.
Find the value of n from which an inequality holds, and put the base case there.

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