Recognition: Divisibility Claims Like '6 Divides n³ − n' Are Induction's Natural Habitat

Read these three problems.

1. Prove that 6 \mid (n^3 - n) for every positive integer n.
2. Prove that 3 \mid (4^n + 5) for every positive integer n.
3. Prove that 11 \mid (10^n + 2 \cdot 3^n) for every positive integer n.

Before you read on, notice that all three have the same shape: "d divides f(n) for every n." A fixed divisor on the left, an n-dependent expression on the right, a universal claim over the positive integers.

Whenever you see this shape, reach for induction immediately. Divisibility-of-f(n) claims are one of the most reliable pattern-matches in all of elementary proof. The inductive step almost always works because divisibility interacts cleanly with the algebraic operations f(n+1) - f(n) usually involves (multiplication, addition, and polynomial shifts).

This article is about recognising the pattern and following the template that almost always closes it.

The signal

A claim is a "divisibility claim" if it has the form:

d \mid f(n) for every n \geq n_0,

where d is a fixed integer and f(n) is an expression that depends on n. Common examples of f:

• polynomials: n^3 - n, n^5 - n, n(n+1)(n+2)
• exponentials: 2^{2n} - 1, 7^n + 1, 5^n - 1
• mixed: 4^n + 5, 10^n - 1, 3^{2n+1} + 2^{n+2}
• combinations of sequences: F_{n+2} F_n - F_{n+1}^2 (Fibonacci)

If the problem asks "is f(n) always divisible by d?" or "prove d \mid f(n)," your default strategy is induction. Not proof by contradiction. Not direct proof. Induction.

Why induction is the natural fit

Two algebraic facts make divisibility and induction mesh perfectly.

Fact 1. d \mid a and d \mid b imply d \mid (a + b) and d \mid (a - b). Divisibility is preserved by addition and subtraction.

Fact 2. d \mid a implies d \mid (ak) for any integer k. Divisibility is preserved by multiplication.

When you compute f(k+1) - f(k) — or more generally, rewrite f(k+1) in terms of f(k) — the operations involved are usually addition, subtraction, and multiplication by integers. Both facts apply. So if d \mid f(k) (hypothesis) and d \mid [f(k+1) - f(k) \cdot \text{integer multiple}] (what you show in the step), then d \mid f(k+1) follows automatically.

This clean interaction is why the pattern works: divisibility is a property that propagates naturally along additive and multiplicative combinations, and the inductive step is built out of exactly those combinations.

The template

Here is the skeleton you can apply to nearly every divisibility-by-induction problem.

Claim. d \mid f(n) for all n \geq 1.

Base case (n = 1). Compute f(1) and check d \mid f(1). Typically one line.

Inductive step. Assume d \mid f(k). Write this as f(k) = d \cdot m for some integer m.

Compute f(k+1) and try to write it as f(k) \cdot (\text{something}) + d \cdot (\text{something else}) or as (\text{multiple of } d) + d \cdot (\text{integer}). The first "something" uses the hypothesis's handle on f(k); the second "something else" is the new piece, and you need it to be a multiple of d.

Specifically, one of these strategies almost always works:

• Strategy A (f is exponential). Factor the base: rewrite f(k+1) = r \cdot f(k) + c where r, c are constants, and show d \mid c.
• Strategy B (f is polynomial). Expand f(k+1) = f(k) + g(k) and show d \mid g(k) directly (often an elementary property of consecutive integers).
• Strategy C (mixed). Decompose f(k+1) using the recurrence or definition of f, then apply A or B to each piece.

Once the rewrite is done, substitute f(k) = d \cdot m using the hypothesis and observe that everything is a multiple of d.

Worked example: 6 \mid (n^3 - n)

Claim. 6 \mid (n^3 - n) for all n \geq 1.

Base case (n = 1). 1^3 - 1 = 0. And 6 \mid 0 (because 0 = 6 \cdot 0). \checkmark

Inductive step. Assume 6 \mid (k^3 - k), so k^3 - k = 6m for some integer m.

Compute (k+1)^3 - (k+1):

Rewrite to expose k^3 - k (the hypothesis's handle):

Why: 3k^2 + 3k factors as 3k(k+1). Among any two consecutive integers k and k+1, exactly one is even — so k(k+1) is always divisible by 2, making 3k(k+1) divisible by 6.

Substitute k^3 - k = 6m:

Since k(k+1) is even, write k(k+1) = 2\ell for some integer \ell. Then 3k(k+1) = 6\ell, and

So 6 \mid [(k+1)^3 - (k+1)]. \checkmark

By induction, 6 \mid (n^3 - n) for all n \geq 1. \square

The step had two moves: expose f(k) inside f(k+1) (by algebraic rearrangement), and show the remainder is also a multiple of d (the 3k(k+1) fact).

When the pattern does not close immediately

Occasionally, the standard move does not land you in a clean multiple of d. Three common adjustments:

1. Check the base case. If f(1) is not divisible by d, the claim is false. Abandon induction — you have a counterexample.
2. Try a smarter rewrite. Sometimes the natural f(k+1) = r \cdot f(k) + c decomposition leaves c not divisible by d. Try rewriting f(k+1) as r \cdot f(k) + r' \cdot g(k) + c where g is a sub-expression you can also prove divisible by d — or strengthen the claim to include g as part of what you are proving.
3. Strengthen the hypothesis. If proving d \mid f(n) alone is awkward, try proving "d \mid f(n) and d \mid g(n)" for some related g. You get both pieces in your hypothesis and more flexibility in the step.

Strategy 3 is the "strengthen the induction" trick that olympiad problems reward; save it for when 1 and 2 fail.

When divisibility claims are not best done by induction

Two exceptions worth naming.

Modular arithmetic can be faster. To show 3 \mid (4^n + 5): work modulo 3. 4 \equiv 1 \pmod{3}, so 4^n \equiv 1 \pmod{3}, so 4^n + 5 \equiv 1 + 5 = 6 \equiv 0 \pmod{3}. Done in three lines without induction.

Once you know modular arithmetic, it often replaces induction for these problems. The induction view is still valuable for the practice it gives in structuring proofs.

Factoring tricks. For n^3 - n = n(n-1)(n+1), you can observe directly that the product of three consecutive integers is always divisible by 6: one of them is a multiple of 3, and at least one is even. No induction needed.

The takeaway is not "always use induction" but "whenever you see a divisibility-of-f(n) claim, induction is the default fallback — and the template is so mechanical that you should write it down before reaching for fancier tools."

The recognition shortcut

Quickly decide which tool to use:

1. Does the claim have the shape "d \mid f(n) for every n"?
   • Yes → Induction is the default.
2. Is f a polynomial that obviously factors (like n(n+1)(n+2))?
   • Yes → Try the direct factoring argument first; fall back to induction.
3. Is f an exponential like r^n + c?
   • Yes → Try modular arithmetic if you know it; otherwise induction.
4. Is f built from a recurrence (like Fibonacci)?
   • Yes → Induction almost certainly, possibly strong.

In a timed exam, option 1 lets you write the first three lines of an induction proof in seconds. That speed matters.

The one-line takeaway

Any claim of the form "d \mid f(n) for every positive integer n" is induction-shaped by default. The template — base case n = 1, step by rewriting f(k+1) to expose f(k) and picking up multiples of d — closes nine out of ten problems. Recognising the pattern in two seconds is the skill.

Divisibility is one of the places where induction shines most reliably. Build the habit of recognising the shape and the template, and these problems turn into a near-automatic exercise.

Related: Mathematical Induction · Number Theory Basics · Recognition Signal: Statements Indexed by n With a Recursive Flavour Are Induction by Default · Intuition: Rewrite the (k+1)-Term to Expose the k-Case — That Is Where the Hypothesis Injects · Modular Arithmetic