Practice Maths

Proof by Induction — Divisibility

← Back to Mathematical Induction›Specialist Maths

Key Terms

Divisibility
d divides n (written d | n) if and only if n = d×m for some integer m.
Inductive hypothesis
Assume f(k) = d×m for some integer m (i.e. f(k) is divisible by d).
Key technique
Express f(k+1) so that f(k) appears; substitute the hypothesis; show the result equals d × (integer).
Method 1 — Factor base
ak+1 = a · ak; group ak − 1 to create the hypothesis term.
Method 2 — Add and subtract
Write f(k+1) = f(k) + [f(k+1) − f(k)]; show both parts are divisible by d.
Integer closure
The sum and product of integers is always an integer; use this to confirm the final expression is d × (integer).

Divisibility — Key Definition

An integer n is divisible by d if and only if n = d · m for some integer m.

Equivalently: d | n   means   n = d×m for some m ∈ ℤ.

To prove f(n) is divisible by d for all n ≥ 1, use induction with P(n): “f(n) = d×m for some integer m.”

The Key Technique — Express f(k+1) in Terms of f(k)

In the inductive step, write f(k+1) so that f(k) appears as a recognisable piece. Then use the hypothesis f(k) = d×m to substitute.

Two common approaches:

Method 1 — Factorise out a base:   ak+1 = a · ak

Method 2 — Add and subtract:   write f(k+1) = f(k) + [f(k+1) − f(k)], then show both parts are divisible by d.

Worked Example — Prove 3n − 1 is divisible by 2 for all n ≥ 1

Step 1 — Base case (n = 1):

31 − 1 = 2 = 2(1)    This is divisible by 2 ✓

Step 2 — Inductive hypothesis:

Assume 3k − 1 = 2m for some integer m (i.e. 3k = 2m + 1).

Step 3 — Inductive step: Show 3k+1 − 1 is divisible by 2.

3k+1 − 1 = 3 · 3k − 1

= 3(2m + 1) − 1     [by the inductive hypothesis]

= 6m + 3 − 1 = 6m + 2 = 2(3m + 1)

Since 3m + 1 is an integer, 3k+1 − 1 is divisible by 2 ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 3n − 1 is divisible by 2 for all n ≥ 1.

Hot Tip: In divisibility induction, the inductive hypothesis tells you f(k) = d×m for some integer m. In the inductive step, your goal is to express f(k+1) entirely in terms of f(k) and then substitute. The two standard techniques are: (1) factor out the base (ak+1 = a·ak) and (2) add and subtract to create f(k) as a recognisable piece.

Setting Up Divisibility Proofs

Divisibility proofs follow the same four steps, but the inductive step requires a different algebraic strategy. You cannot just “add the next term” as in summation proofs. Instead, the goal is to show that f(k+1) can be written as a multiple of d, given that f(k) is a multiple of d.

Method 1: Factorising the Base (For Exponential Expressions)

For expressions like an − bn or an − 1, use:

ak+1 = a · ak

Then substitute the inductive hypothesis ak = 1 + d×m (if you assumed ak − 1 = dm):

ak+1 − 1 = a · ak − 1 = a(1 + dm) − 1 = (a − 1) + adm

If d | (a − 1) and d | adm, then d | ak+1 − 1.

Hot Tip — The Substitution Trick:
When proving an − 1 is divisible by (a − 1), the hypothesis gives ak = 1 + (a−1)m. Substitute this wherever ak appears and expand. All remaining terms will contain (a − 1) as a factor.

Method 2: Add and Subtract (For Polynomial Expressions)

For expressions like n³ + 2n or n(n+1)(n+2), write f(k+1) and then introduce f(k) by adding and subtracting the same quantity:

f(k+1) = [f(k+1) − f(k)] + f(k)

Show f(k+1) − f(k) is divisible by d directly (it usually simplifies to a small expression), then use the hypothesis to handle f(k).

Writing the Hypothesis Correctly

Always write the hypothesis in the form: “f(k) = d × m for some integer m.” Do not leave it as “f(k) is divisible by d.” The explicit form f(k) = dm is what you substitute in Step 3.

Type of ExpressionRecommended Strategy
an − 1Write ak+1 = a · ak, substitute ak = 1 + dm
an − bnWrite ak+1 − bk+1 = a(ak − bk) + bk(a−b)
Polynomial in nCompute f(k+1) − f(k), simplify, show divisible by d
Product n(n+1)…Expand f(k+1) directly; group to isolate f(k)

Common Mistake: Not Establishing That the Remainder is an Integer

After factoring out d, you must confirm that the remaining factor is an integer. For example, if you reach d(3m + k + 1), you must note that “since m and k are integers, 3m + k + 1 is also an integer.” Without this, the argument is incomplete.

Mastery Practice

  1. Fluency

    Q1 — Powers of 2 are Odd Differences

    Prove by mathematical induction that 2n − 1 is odd (i.e. not divisible by 2) for all integers n ≥ 1.

    Hint: show 2n − 1 = 2t − 1 for some integer t, i.e. it is always of the form “even minus 1”.

  2. Fluency

    Q2 — n³ − n is Divisible by 3

    Prove by mathematical induction that n³ − n is divisible by 3 for all integers n ≥ 1.

  3. Fluency

    Q3 — 4n − 1 is Divisible by 3

    Prove by mathematical induction that 4n − 1 is divisible by 3 for all integers n ≥ 1.

  4. Fluency

    Q4 — 7n − 1 is Divisible by 6

    Prove by mathematical induction that 7n − 1 is divisible by 6 for all integers n ≥ 1.

  5. Understanding

    Q5 — 3n − 1 is Divisible by 2

    Prove by mathematical induction that 3n − 1 is divisible by 2 for all integers n ≥ 1.

  6. Understanding

    Q6 — 5n − 1 is Divisible by 4

    Prove by mathematical induction that 5n − 1 is divisible by 4 for all integers n ≥ 1.

  7. Understanding

    Q7 — n(n+1)(n+2) is Divisible by 6

    Prove by mathematical induction that n(n+1)(n+2) is divisible by 6 for all integers n ≥ 1.

  8. Understanding

    Q8 — 22n − 1 is Divisible by 3

    Prove by mathematical induction that 22n − 1 is divisible by 3 for all integers n ≥ 1.

    Hint: 22(k+1) = 4 · 22k.

  9. Problem Solving

    Q9 — Two Divisibility Results for Powers of 6

    (a) Prove by mathematical induction that 6n − 1 is divisible by 5 for all n ≥ 1.

    (b) Hence, or otherwise, prove that 6n + 4 is also divisible by 5 for all n ≥ 1.

  10. Problem Solving

    Q10 — n³ + 2n is Divisible by 3: Two Approaches

    Prove that n³ + 2n is divisible by 3 for all integers n ≥ 1 using:

    (a) Mathematical induction.

    (b) Direct algebraic reasoning (factorisation), without induction.

See Answers ➔