Proof by induction: divisibility

Strategy

Let f(n) be the expression. The neatest route is to consider f(k + 1) - f(k) (or f(k + 1) - m f(k) for a suitable m), show it is a multiple of the divisor, then use

f(k + 1) = [f(k + 1) - f(k)] + f(k).

If both parts are divisible, so is f(k + 1).

Example

Prove 3²ⁿ + 11 is divisible by 4.

n = 1: 9 + 11 = 20 = 4 × 5. True.

Assume f(k) = 3^2k + 11 is divisible by 4.

f(k + 1) - f(k) = 3^2k+2 - 3^2k = 9 × 3^2k - 3^2k = 8 × 3^2k, which is divisible by 4.

So f(k + 1) = 8 × 3^2k + f(k) is divisible by 4.

Conclusion as usual.

Handling powers

Write a^k+1 = a × a^k and a^(2(k+1)) = a² × a^2k. When the expression has a linear part, such as 5ⁿ + 8n + 3, the difference f(k + 1) - f(k) is 4 × 5^k + 8, still clearly divisible by 4.

Worked example

Prove by induction that 5ⁿ + 8n + 3 is divisible by 4 for all positive integers n.

1. n = 1: 5 + 8 + 3 = 16 = 4 × 4. True.
2. Assume f(k) = 5^k + 8k + 3 is divisible by 4.
3. f(k + 1) - f(k) = 5^k+1 - 5^k + 8 = 4 × 5^k + 8 = 4(5^k + 2).
4. f(k + 1) = 4(5^k + 2) + f(k), a sum of multiples of 4. True for n = 1 and true for k implies true for k + 1, so true for all positive integers n.

Answer: Proved

Check yourself

1. f(n) = 3²ⁿ + 11. Find f(1).
   Show answer

   20. 3² + 11 = 20.

2. f(n) = 3²ⁿ + 11. f(k + 1) - f(k) = a × 3^2k. Find a.
   Show answer

   8. 3^2k+2 = 9 × 3^2k, so the difference is 9 × 3^2k - 3^2k = 8 × 3^2k.

3. g(n) = 5ⁿ + 8n + 3. g(k + 1) - g(k) = 4 × 5^k + c. Find c.
   Show answer

   8. 5^k+1 - 5^k = 4 × 5^k, and 8(k + 1) - 8k = 8. So c = 8.

4. Why does f(k + 1) - f(k) being divisible by 4, together with the assumption, prove f(k + 1) is divisible by 4?
   • Because f(k + 1) is larger than f(k)
   • Because 4 divides every power of 3
   • Because f(1) = 20
   • f(k + 1) = [f(k + 1) - f(k)] + f(k), a sum of two multiples of 4
   Show answer

   f(k + 1) = [f(k + 1) - f(k)] + f(k), a sum of two multiples of 4. The sum of two multiples of 4 is a multiple of 4.

5. 7ⁿ - 3ⁿ is divisible by d for every positive integer n, and d is the largest such number. Find d by looking at n = 1 and n = 2.
   Show answer

   4. n = 1 gives 4 and n = 2 gives 49 - 9 = 40. The highest common factor is 4. (Induction confirms divisibility by 4.)

6. Which is equal to 3^(2(k+1))?
   • 3 × 3^2k
   • 3^2k + 2
   • 6 × 3^2k
   • 9 × 3^2k
   Show answer

   9 × 3^2k. 3^{2k + 2} = 3^2k × 3².

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics, Further Mathematics and Pure Mathematics specification (issue 3), Unit FP1
• Pearson Edexcel IAL Further Pure Mathematics 1 scheme of work

Last updated 8 November 2026. Spotted a mistake? Tell us.