Practice Maths

← Proof by Mathematical Induction

Induction for Divisibility and Inequalities

Key Terms

Divisibility induction
To prove “d | f(n) for all n ≥ n₀”, write f(k+1) in terms of f(k) and show the remainder is also divisible by d.
Key trick
Express f(k+1) = A × f(k) + B where B is divisible by d, then conclude f(k+1) is divisible by d.
Inequality induction
Assume P(k): f(k) > g(k), then show f(k+1) > g(k+1) by relating f(k+1) to f(k) using the inductive hypothesis.
For inequalities, you often use: if a > b and c > d (with appropriate signs), then a + c > b + d.
The base case for inequalities must also verify the inequality, not just equality.
Divisibility Notation:
• We write d | n to mean “d divides n”, i.e. n = d · m for some integer m.
• If d | a and d | b, then d | (a + b) and d | (a − b).
• If d | a, then d | (ca) for any integer c.
Hot Tip For divisibility proofs, the key move is: write f(k+1) = (something) × f(k) + (something divisible by d). Then since f(k) is divisible by d (by the inductive hypothesis), and the added term is also divisible by d, the whole expression is divisible by d.

Worked Example 1 — Prove 3 | (4n − 1) for all n ≥ 1

Base case (n = 1): 41 − 1 = 3. Clearly 3 | 3. ✓

Inductive hypothesis: Assume 3 | (4k − 1) for some integer k ≥ 1, i.e. 4k − 1 = 3m for some integer m.

Inductive step: Consider 4k+1 − 1 = 4 × 4k − 1 = 4(4k − 1) + 3.

= 4(3m) + 3     [by inductive hypothesis]

= 3(4m + 1).

Since 4m + 1 is an integer, 3 | (4k+1 − 1). ✓

Conclusion: By mathematical induction, 3 | (4n − 1) for all n ≥ 1.

Worked Example 2 — Prove n² > 2n + 1 for all n ≥ 3

Base case (n = 3): LHS = 9. RHS = 7. 9 > 7. ✓

Inductive hypothesis: Assume k² > 2k + 1 for some integer k ≥ 3.

Inductive step: We must show (k+1)² > 2(k+1) + 1 = 2k + 3.

(k+1)² = k² + 2k + 1 > (2k+1) + 2k + 1 = 4k + 2 ≥ 2k + 3 (since 2k ≥ 1 for k ≥ 1).

Actually more directly: (k+1)² = k² + 2k + 1 > (2k+1) + 2k + 1 = 4k + 2 > 2k + 3 for k ≥ 3. ✓

Conclusion: By mathematical induction, n² > 2n + 1 for all n ≥ 3.

Divisibility Proofs by Induction

Divisibility is one of the most common applications of mathematical induction in senior mathematics. A divisibility statement has the form: “For all integers n ≥ n₀, d divides f(n)”, written d | f(n). The approach is always the same: express f(k+1) in terms of f(k), then use the inductive hypothesis to extract a factor of d.

The fundamental algebraic tool is: if d | a and d | b, then d | (a + b). So if you can write f(k+1) = (multiple of d) + (multiple of f(k)), and the inductive hypothesis says d | f(k), then d | f(k+1).

The Standard Technique: Isolate f(k)

For exponential divisibility proofs of the form f(n) = an + c, the standard manipulation is:

f(k+1) = ak+1 + c = a × ak + c = a(ak + c) − ac + c = a × f(k) + c(1 − a).

Since d | f(k) by the inductive hypothesis, we need d | c(1−a). This is verified at the start. Let’s apply this to 6 | (7n − 1):

7k+1 − 1 = 7(7k − 1) + 6 = 7 × f(k) + 6. Since 6 | f(k) and 6 | 6, we have 6 | f(k+1).

Proving Divisibility by Larger Numbers

When proving divisibility by 8, 12, etc., you need both f(k) terms and the remainder to contribute multiples. For example, to prove 8 | (9n − 1):

9k+1 − 1 = 9(9k − 1) + 8 = 9 × 8m + 8 = 8(9m + 1).

This is clean because 9 − 1 = 8 exactly matches our divisor. When the remainder after isolating f(k) is not itself divisible by d, you must reconsider your factorisation — perhaps factor differently.

Inequality Proofs by Induction

Inequality induction requires more care than equality induction. The inductive step is not an equation to verify but an inequality to establish. The key reasoning pattern is:

  1. Write (k+1)th expression in terms of the kth expression.
  2. Apply the inductive hypothesis to replace f(k) with a bound.
  3. Show the resulting expression satisfies the inequality for k+1.

You may need to use additional facts such as “since k ≥ 4, we have k > 2”. These must be explicitly justified by reference to the domain of n.

Proving n! > 2n for n ≥ 4

This is a classic. Base case (n = 4): 4! = 24 > 16 = 24. ✓

Inductive step: Assume k! > 2k for some k ≥ 4. Then:

(k+1)! = (k+1) × k! > (k+1) × 2k > 2 × 2k = 2k+1.

The crucial step “k+1 > 2” is valid because k ≥ 4 implies k+1 ≥ 5 > 2.

Conclusion: By induction, n! > 2n for all n ≥ 4.

Choosing the Right Base Case

For inequalities, the base case is often not n = 1. You must identify the smallest n for which the inequality holds, verify it directly, and state clearly that this is your base case. If a statement asks for “all n ≥ 4”, you must use n = 4 as the base case — using n = 1 is incorrect because the statement may be false for n < 4.

Common Errors in Inequality Induction

  • Using “≥” when the statement is strict “>”: Track which type of inequality you need throughout the proof.
  • Unjustified bounds: Every inequality step must be justified. If you write a > b, explain why. If you use k ≥ n₀, invoke this explicitly.
  • Forgetting the base case: Especially when n₀ ≠ 1, students often forget to verify the base case explicitly.
Exam Tip: For divisibility, after writing f(k+1) = A × f(k) + B, explicitly state “since d | f(k) by the inductive hypothesis, we have d | A×f(k)”, and then “since d | B (which can be checked directly)”, therefore d | f(k+1). This two-step reasoning scores full marks.
Exam Tip: For inequalities, you are allowed to use stronger intermediate results. E.g. if you need to show f(k+1) > g(k+1), and you can show f(k+1) > h(k+1) ≥ g(k+1), this is perfectly valid. Often the first bound is obtained from the inductive hypothesis.

Mastery Practice

See Answers ➔

  1. Verify the base case and inductive hypothesis for each divisibility statement. Fluency

    1. (a) 3 | (4n − 1) for all n ≥ 1
    2. (b) 5 | (6n − 1) for all n ≥ 1
    3. (c) 7 | (8n − 1) for all n ≥ 1

  2. Complete the inductive step. Fluency

    Given that 5 | (6k − 1) for some integer k ≥ 1, show that 5 | (6k+1 − 1). Write out the factorisation explicitly.

  3. Prove by mathematical induction. Fluency

    Prove that for all integers n ≥ 1: 3 | (n3 − n).

  4. Verify the base case for the inequality. Fluency

    For each inequality, identify the correct base case and verify it directly:

    1. (a) n! > 2n for n ≥ 4
    2. (b) 2n > n2 for n ≥ 5
    3. (c) n2 > 2n + 1 for n ≥ 3

  5. Prove by mathematical induction. Understanding

    Prove that for all integers n ≥ 1: 6 | (n3 − n). (Note: n3−n = n(n−1)(n+1), the product of three consecutive integers.)

  6. Prove the inequality by induction. Understanding

    Prove that n! > 2n for all integers n ≥ 4. You must clearly state the base case, inductive hypothesis, and inductive step.

  7. Prove the inequality by induction. Understanding

    Prove that 2n > n2 for all integers n ≥ 5.

  8. Prove the divisibility result. Understanding

    Prove that for all integers n ≥ 1: 8 | (9n − 1).

  9. Prove the divisibility result using a more complex factorisation. Problem Solving

    Prove that for all integers n ≥ 1: 3 | (n3 + 2n). [Hint: n3 + 2n = n(n2−1) + 3n = n(n−1)(n+1) + 3n.]

  10. Multi-part challenge. Problem Solving

    Challenge.
    1. (a) Prove by induction that 4 | (5n − 1) for all n ≥ 1.
    2. (b) Prove by induction that n2 < 2n is false for n = 4. Then prove 2n > n2 fails for n = 4 and is only true for n ≥ 5 (use part of Q7 reasoning).
    3. (c) Hence prove that for all n ≥ 5: (5n−1) / 4 > n2. [Hint: combine results from (a) and 2n > n2; first show 5n−1 ≥ 4×2n for n≥5.]