Divisibility proofs | Year 12

01 / LEARN

The idea, step by step

Turn divisibility into an equation

If d divides A(k), write A(k)=dq for an integer q. This expresses exactly what the induction hypothesis gives. To prove the next case, show d times another integer, not just a decimal approximation.

For powers, add and subtract a useful intermediate term. For a polynomial, expand A(k+1)-A(k) to isolate the part added to the assumed divisible expression.

Explain the integer fact

For n^3-n, the added contribution is 3k(k+1). One of two consecutive integers is even, making this contribution divisible by six. State that fact explicitly.

Zero and negative multiples count as divisible values. A rational multiplier alone is insufficient; make its integrality clear.

A common trap

Forgetting that the multiplier is an integer.

Instead: State the integer and show that the new multiplier is also an integer.

02 / WORKED EXAMPLES

See the thinking

Example 1

Power differences

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

$n = 1$ gives $3$ .
Assume $5^{k} - 2^{k} = 3 q$ for an integer $q$ .
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$ .
Conclude all positive integers by induction.

5^{n} - 2^{n}

is divisible by

3

is true throughout the stated domain.

Example 2

Divisibility by six

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

At $n = 1$ , the value is $0 = 6 (0)$ .
Assume $k^{3} - k = 6 q$ for an integer $q$ .
${(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)$ .
Conclude all positive integers by induction.

n^{3} - n

is divisible by

6

is true throughout the stated domain.

Check your understanding

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

Show answer

One of k and k+1 is even.

Their product is twice an integer.

03 / WORKSHEET

Your turn

6 questions · 36 marks · Work at your own pace.

Worksheet PDF 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…

Continue learning

Identities involving powers and integers

Next lesson

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 ↗

Back to Mathematical induction