Mathematical induction for divisibility: standard technique and algebraic restructuring

What this dot point is asking

NESA wants you to use induction to prove that an expression $E(n)$ built from an integer parameter $n$ is always divisible by a fixed integer $d$, for every positive integer $n$. The work is concentrated in the inductive step, where the whole game is to rewrite $E(k + 1)$ so that one piece is the $E(k)$ the hypothesis already controls and the rest is visibly a multiple of $d$. Saying "it is divisible because the hypothesis says so" is not enough; you have to display the factor of $d$ explicitly.

The answer

What "divisible by $d$" means in a proof

Divisibility is the statement that $E(n)$ is an exact multiple of $d$, written $E(n) = d \times (\text{integer})$. Translating the word "divisible" into that algebraic form is the single most important move, because it gives you something concrete to work with. So the hypothesis is never just "assume $E(k)$ is divisible by $d$"; it is "assume $E(k) = d M$ for some integer $M$", and the goal of the step is to reach "$E(k + 1) = d \times (\text{some integer})$".

The four-part structure

To prove $E(n)$ is divisible by $d$ for all positive integers $n$, follow the same four parts as every other induction:

1. Base case: verify $E(1)$ is divisible by $d$ by direct substitution, showing the actual multiple.
2. Inductive hypothesis: assume $E(k)$ is divisible by $d$, that is $E(k) = d M$ for some integer $M$.
3. Inductive step: show $E(k + 1)$ is divisible by $d$, by writing it in a form that uses $E(k) = d M$ plus a term that is itself a multiple of $d$.
4. Conclusion: by the principle of mathematical induction, $E(n)$ is divisible by $d$ for all positive integers $n$.

The add-and-subtract trick (the core technique)

The add-and-subtract trick is the reliable way to manufacture the $E(k)$ chunk inside $E(k + 1)$. You start from $E(k + 1)$, and you add and subtract whatever is needed to make $E(k)$ appear, so that the expression splits into "$E(k)$" plus "a leftover", and you then check the leftover is a multiple of $d$. Because you add and subtract the same quantity, you have changed nothing, only the grouping.

The classic illustration is $a^n - 1$ being divisible by $a - 1$. Step the power up by writing $a^{k + 1} = a \cdot a^k$, then add and subtract $a$ so that $a^k - 1$ appears:

The first piece $a(a^k - 1)$ contains $a^k - 1 = E(k)$, which the hypothesis says is a multiple of $a - 1$; the second piece is $a - 1$ itself, plainly a multiple of $a - 1$. The sum of two multiples of $a - 1$ is a multiple of $a - 1$, so $E(k + 1)$ is too. That single identity is worth memorising as the template.

The multiplier method for exponentials

For an expression with a single exponential like $5^n$, the fastest route is the multiplier method: pull out one factor of the base to step the exponent up, then substitute the hypothesis. From $E(k) = 5^k - 1 = 4M$, rearrange to $5^k = 4M + 1$, then

The factor of $4$ is now explicit. The same idea handles $a^{2n}$ by writing $a^{2(k + 1)} = a^2 \cdot a^{2k}$, and so on.

Two exponentials: split the larger base

When the expression has two different bases, such as $7^n - 3^n$ divisible by $4$, neither one alone matches the hypothesis. The trick is to write the larger base as "smaller base plus the difference": here $7 = 4 + 3$, so $7 \cdot 7^k = (4 + 3)7^k = 4 \cdot 7^k + 3 \cdot 7^k$. The $3 \cdot 7^k$ then pairs with $-3 \cdot 3^k$ to rebuild $3(7^k - 3^k) = 3 E(k)$, and the $4 \cdot 7^k$ is an obvious multiple of $4$. This is the add-and-subtract idea wearing different clothes.

A different starting integer

If the statement says "for all $n \ge 2$" or "for all $n \ge 0$", start the base case at the smallest valid $n$ and run the step from there. The inductive step still goes from $k$ to $k + 1$ exactly as before; only the base value changes.

How exam questions ask about divisibility

• "Prove that $E(n)$ is divisible by $d$ for all positive integers $n$": the standard wording. Use the four parts; write the hypothesis as $E(k) = d M$.
• "Show that $d \mid E(n)$" or "... is a multiple of $d$": identical task in different notation; $d \mid E(n)$ just means $d$ divides $E(n)$.
• "Prove that $E(n)$ is even / odd": divisibility by $2$. "Even" means $E(k) = 2M$; "odd" means $E(k) = 2M + 1$.
• "Hence show that $E(n)$ is divisible by $d$" after an earlier algebra part: the earlier part usually hands you the factorisation you need for the step.
• "Prove $E(n)$ is divisible by $12$" (a composite): the method is unchanged; aim to display a factor of $12$. Sometimes it is easier to show divisibility by $3$ and by $4$ separately, but in HSC you can usually reach a factor of $12$ directly.

Edge cases and what-ifs

• Composite divisors. For divisibility by a composite such as $6$ or $12$, you can either reach the factor directly, or, if the algebra resists, prove divisibility by the coprime factors separately (for $6$, by $2$ and by $3$) and combine. In HSC the direct factor is almost always reachable.
• Using a consecutive-integer fact. Some proofs finish faster by noting that a product of consecutive integers is divisible by a small number, for example $k(k + 1)$ is always even, so $3k(k + 1)$ is divisible by $6$. State the fact you are using.
• Base case not at $n = 1$: When the claim starts at $n = 0$ or $n = 2$, verify the base there. Everything else is identical.
• Negative or zero multiples. A multiple of $d$ may be $0$ (as in $n^3 - n$ at $n = 1$) or negative; both still count as divisible. Do not be thrown if the base-case value is $0$.