Divisibility proofs | Year 12

01 / LEARN

Understand the idea.

Turn divisibility into an equation

To prove divisibility, turn the statement into an integer equation: $d ∣ A (k)$ means $A (k) = d q$ for some $q \in ℤ$ . The next expression must also become $d$ times an integer.

For powers, rewrite the successor using the old power difference. For polynomial expressions, expand $A (k + 1)$ and separate $A (k)$ . This exposes exactly which extra quantity must be divisible by $d$ .

Explain the integer fact

The multiplier is part of the proof. For example, $3 k (k + 1)$ is a multiple of six because consecutive integers include an even one; writing $k (k + 1) = 2 t$ makes the integer $t$ explicit.

Zero is divisible by every nonzero integer, so a zero base value is valid. After forming the new multiple, explain why its multiplier is an integer and finish the induction over the stated domain.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

Power differences

Prove $5^{n} - 2^{n}$ is divisible by $3$ for $n \geq 1$ .

Worked solution

1
Check the base case.
$5^{1} - 2^{1} = 3 = 3 \cdot 1.$
The initial difference is a multiple of three.
2
Express the hypothesis as a multiple.
$5^{k} - 2^{k} = 3 q, q \in ℤ, k \in ℤ, k \geq 1.$
Divisibility requires an integer multiplier.
3
Expose the old difference.
$\begin{aligned} 5^{k + 1} - 2^{k + 1} & = 5 \cdot 5^{k} - 2 \cdot 2^{k} \\ = 5 (5^{k} - 2^{k}) + 3 \cdot 2^{k} . \end{aligned}$
Adding and subtracting $5 \cdot 2^{k}$ creates the expression in the hypothesis.
4
Produce the next integer multiple.
$5^{k + 1} - 2^{k + 1} = 15 q + 3 \cdot 2^{k} = 3 (5 q + 2^{k}) .$
The quantity $5 q + 2^{k}$ is an integer for every allowed $k$ .
5
Conclude by induction.
$3 ∣ (5^{n} - 2^{n}) (n \in ℤ, n \geq 1) .$
The checked base and successor implication establish the entire domain.

Answer

$5^{n} - 2^{n}$ is divisible by $3$ is true throughout the stated domain.

EXAMPLE 02

Divisibility by six

Prove $n^{3} - n$ is divisible by $6$ for $n \geq 1$ .

Worked solution

1
Verify the first case.
$1^{3} - 1 = 0 = 6 \cdot 0.$
Zero is an integer multiple of six.
2
State the integer hypothesis.
$k^{3} - k = 6 q, q \in ℤ, k \in ℤ, k \geq 1.$
This is the divisibility statement at the arbitrary old index.
3
Expand and isolate the old expression.
$\begin{aligned} {(k + 1)}^{3} - (k + 1) & = k^{3} + 3 k^{2} + 2 k \\ = (k^{3} - k) + 3 k (k + 1) . \end{aligned}$
The extra contribution after the old case is $3 k (k + 1)$ .
4
Use the parity of consecutive integers.
$k (k + 1) = 2 t (t \in ℤ), {(k + 1)}^{3} - (k + 1) = 6 q + 6 t = 6 (q + t) .$
One of $k$ and $k + 1$ is even, so the new multiplier $q + t$ is an integer.
5
Complete the induction.
$6 ∣ (n^{3} - n) (n \in ℤ, n \geq 1) .$
The base and proved successor step give every positive-integer case.

Answer

$n^{3} - n$ is divisible by $6$ is true throughout the stated domain.

03 / YOUR TURN

Try it yourself.

Check your understanding

Why does six divide $3 k (k + 1)$ ?

Show answer & reasoning

One of k and k+1 is even.

Consecutive integers cannot both be odd, so $k (k + 1) = 2 t$ for an integer $t$ . Therefore $3 k (k + 1) = 6 t$ , a multiple of six.

Keep practising

6 worksheet questions · 36 marks

Open worksheet Worked solutions

Read the questions online

Prove $5^{n} - 1$ is divisible by $4$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $5^{n} - 2^{n}$ is divisible by $3$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $8^{n} - 3^{n}$ is divisible by $5$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $n^{3} - n$ is divisible by $6$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $n^{3} + 2 n$ is divisible by $3$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $7^{n} - {(- 1)}^{n}$ is divisible by $8$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

Prove $5^{n} - 1$ is divisible by $4$ for all integers $n \geq 1$ .
6 marks
(a) $n = 1$ gives $4$ .
(a) Assume $5^{k} - 1 = 4 q$ for an integer $q$ .
(b) Write $5^{k + 1} - 1 = 5 (5^{k} - 1) + 4$ .
(b) This is $4 (5 q + 1)$ , an integer multiple of $4$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  $n = 1$ gives $4$ .
  Assume $5^{k} - 1 = 4 q$ for an integer $q$ .
  $n = 1$ gives $4$ . Assume $5^{k} - 1 = 4 q$ for an integer $q$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Write $5^{k + 1} - 1 = 5 (5^{k} - 1) + 4$ .
  This is $4 (5 q + 1)$ , an integer multiple of $4$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) $n = 1$ gives $4$ . Assume $5^{k} - 1 = 4 q$ for an integer $q$ . (b) The statement holds for all positive integers.
Prove $5^{n} - 2^{n}$ is divisible by $3$ for all integers $n \geq 1$ .
6 marks
(a) $n = 1$ gives $3$ .
(a) Assume $5^{k} - 2^{k} = 3 q$ for an integer $q$ .
(b) Write $5^{k + 1} - 2^{k + 1} = 5 (5^{k} - 2^{k}) + (5 - 2) 2^{k}$ .
(b) This is $3 (5 q + 2^{k})$ , an integer multiple of $3$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  $n = 1$ gives $3$ .
  Assume $5^{k} - 2^{k} = 3 q$ for an integer $q$ .
  $n = 1$ gives $3$ . Assume $5^{k} - 2^{k} = 3 q$ for an integer $q$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Write $5^{k + 1} - 2^{k + 1} = 5 (5^{k} - 2^{k}) + (5 - 2) 2^{k}$ .
  This is $3 (5 q + 2^{k})$ , an integer multiple of $3$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) $n = 1$ gives $3$ . Assume $5^{k} - 2^{k} = 3 q$ for an integer $q$ . (b) The statement holds for all positive integers.
Prove $8^{n} - 3^{n}$ is divisible by $5$ for all integers $n \geq 1$ .
6 marks
(a) $n = 1$ gives $5$ .
(a) Assume $8^{k} - 3^{k} = 5 q$ for an integer $q$ .
(b) Write $8^{k + 1} - 3^{k + 1} = 8 (8^{k} - 3^{k}) + (8 - 3) 3^{k}$ .
(b) This is $5 (8 q + 3^{k})$ , an integer multiple of $5$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  $n = 1$ gives $5$ .
  Assume $8^{k} - 3^{k} = 5 q$ for an integer $q$ .
  $n = 1$ gives $5$ . Assume $8^{k} - 3^{k} = 5 q$ for an integer $q$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Write $8^{k + 1} - 3^{k + 1} = 8 (8^{k} - 3^{k}) + (8 - 3) 3^{k}$ .
  This is $5 (8 q + 3^{k})$ , an integer multiple of $5$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) $n = 1$ gives $5$ . Assume $8^{k} - 3^{k} = 5 q$ for an integer $q$ . (b) The statement holds for all positive integers.
Prove $n^{3} - n$ is divisible by $6$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , the value is $0 = 6 (0)$ .
(a) Assume $k^{3} - k = 6 q$ for an integer $q$ .
(b) ${(k + 1)}^{3} - (k + 1) = (k^{3} - k) + 3 k (k + 1)$ .
(b) One of consecutive integers $k, k + 1$ is even, so $k (k + 1) = 2 t$ for an integer $t$ .
(b) The next value is $6 (q + t)$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , the value is $0 = 6 (0)$ .
  Assume $k^{3} - k = 6 q$ for an integer $q$ .
  At $n = 1$ , the value is $0 = 6 (0)$ . Assume $k^{3} - k = 6 q$ for an integer $q$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  ${(k + 1)}^{3} - (k + 1) = (k^{3} - k) + 3 k (k + 1)$ .
  One of consecutive integers $k, k + 1$ is even, so $k (k + 1) = 2 t$ for an integer $t$ .
  The next value is $6 (q + t)$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , the value is $0 = 6 (0)$ . Assume $k^{3} - k = 6 q$ for an integer $q$ . (b) The statement holds for all positive integers.
Prove $n^{3} + 2 n$ is divisible by $3$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , the value is $3$ .
(a) Assume $k^{3} + 2 k = 3 q$ for an integer $q$ .
(b) ${(k + 1)}^{3} + 2 (k + 1) = (k^{3} + 2 k) + 3 (k^{2} + k + 1)$ .
(b) This is $3 (q + k^{2} + k + 1)$ , an integer multiple of $3$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , the value is $3$ .
  Assume $k^{3} + 2 k = 3 q$ for an integer $q$ .
  At $n = 1$ , the value is $3$ . Assume $k^{3} + 2 k = 3 q$ for an integer $q$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  ${(k + 1)}^{3} + 2 (k + 1) = (k^{3} + 2 k) + 3 (k^{2} + k + 1)$ .
  This is $3 (q + k^{2} + k + 1)$ , an integer multiple of $3$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , the value is $3$ . Assume $k^{3} + 2 k = 3 q$ for an integer $q$ . (b) The statement holds for all positive integers.
Prove $7^{n} - {(- 1)}^{n}$ is divisible by $8$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , the value is $8$ .
(a) Assume $7^{k} - {(- 1)}^{k} = 8 q$ for an integer $q$ .
(b) $7^{k + 1} - {(- 1)}^{k + 1} = 7 [7^{k} - {(- 1)}^{k}] + 8 {(- 1)}^{k}$ .
(b) This is $8 [7 q + {(- 1)}^{k}]$ , divisible by $8$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , the value is $8$ .
  Assume $7^{k} - {(- 1)}^{k} = 8 q$ for an integer $q$ .
  At $n = 1$ , the value is $8$ . Assume $7^{k} - {(- 1)}^{k} = 8 q$ for an integer $q$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  $7^{k + 1} - {(- 1)}^{k + 1} = 7 [7^{k} - {(- 1)}^{k}] + 8 {(- 1)}^{k}$ .
  This is $8 [7 q + {(- 1)}^{k}]$ , divisible by $8$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , the value is $8$ . Assume $7^{k} - {(- 1)}^{k} = 8 q$ for an integer $q$ . (b) The statement holds for all positive integers.

Checking saved progress…

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 2 Specialist mathematical induction. Explicit summation, power and divisibility identities; induction of inequalities or recursive formulae is not required.

Official curriculum source ↗

In this lesson

Understand the idea.

Turn divisibility into an equation

Explain the integer fact

See the method in action.

Power differences

Check the base case.

Express the hypothesis as a multiple.

Expose the old difference.

Produce the next integer multiple.

Conclude by induction.

Divisibility by six

Verify the first case.

State the integer hypothesis.

Expand and isolate the old expression.

Use the parity of consecutive integers.

Complete the induction.

Try it yourself.

Check your understanding

Keep practising