Maths › Further proof › Induction: divisibility and matrices
Induction: divisibility and matrices
The same domino argument aimed at new targets: expressions that stay divisible by a fixed number, and matrix powers that follow a pattern.
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.
- Choose the rearrangement that exposes the inductive hypothesis in each type.
WHAT YOU PROBABLY THINK
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.
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. ∎
The rearrangement 8 × 8k − 1 = 8(8k − 1) + 7 is the move to practise: pull out a multiple of the assumed expression, and what remains must be checked divisible on its own. Writing the hypothesis as 7m, with m an integer, keeps the final factorisation honest.
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.
YOUR TURN
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. ∎ The multiplication must be shown entry by entry; asserting the product is where these proofs lose their method mark.
The opening claim fails at the door. Without a base case the argument proves nothing: 'each domino topples the next' is useless if no domino ever falls. A claim can pass the inductive step and still be false for every n, so both obligations must appear in every proof.
THE EXAM BIT
- 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 every flavour: base case, inheritance, 'by induction'.
CHECK YOURSELF
Prove by induction that 9n + 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
B
a
s
e
c
a
s
e
,
n
=
1
:
9
+
1
1
=
2
0
=
4
×
5
,
t
r
u
e
.
A
s
s
u
m
e
9
{
{
^
{
k
}
}
}
+
1
1
=
4
m
f
o
r
a
n
i
n
t
e
g
e
r
m
.
T
h
e
n
9
{
{
^
{
k
+
1
}
}
}
+
1
1
=
9
(
9
{
{
^
{
k
}
}
}
+
1
1
)
−
8
8
=
9
×
4
m
−
8
8
=
4
(
9
m
−
2
2
)
,
a
m
u
l
t
i
p
l
e
o
f
4
.
T
r
u
e
f
o
r
n
=
1
a
n
d
i
n
h
e
r
i
t
e
d
f
r
o
m
k
t
o
k
+
1
,
s
o
t
r
u
e
f
o
r
a
l
l
p
o
s
i
t
i
v
e
i
n
t
e
g
e
r
s
n
b
y
i
n
d
u
c
t
i
o
n
.
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, 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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Prove divisibility statements by induction, using the subtract-a-multiple rearrangement.
- Prove a formula for the nth power of a matrix by induction.
- Choose the rearrangement that exposes the inductive hypothesis in each type.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.