Prove divisibility statements involving an integer parameter $n$ using mathematical induction

What this dot point is asking

NESA wants you to use induction to prove that an expression involving an integer parameter $n$ is divisible by a fixed integer. The trick is in the inductive step: write $E(k + 1)$ in terms of $E(k)$ plus a term that is plainly divisible.

The answer

The structure

To prove $E(n)$ is divisible by $d$ for all positive integers $n$:

1. Base case: Verify $E(1)$ is divisible by $d$ by direct substitution.
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$. Write $E(k + 1)$ in a form that uses $E(k) = d M$ from the hypothesis, 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 standard algebraic move

For $E(k + 1)$, the most common technique is:

• Factor out the common growth term (multiply by the base of the exponent, or expand the recurrence).
• Rewrite using $E(k) = d M$ from the hypothesis.
• Show the remaining algebra produces another multiple of $d$.

Example pattern: $a^n - 1$ divisible by IMATH_27

For $a^n - 1$ divisible by $a - 1$ (for any integer $a$): the standard manipulation is

By the inductive hypothesis, $a^k - 1$ is a multiple of $a - 1$. Adding another $(a - 1)$ keeps it a multiple.

Example pattern: combine two cases

For statements like $n^3 + 2 n$ divisible by $3$, expand $(k + 1)^3 + 2(k + 1)$ and rewrite as $k^3 + 2 k$ plus extra terms. The hypothesis covers $k^3 + 2 k$; show the extra is a multiple of $3$.

Different starting integer

If the statement is "for all $n \ge 2$" or "for all $n \ge 5$", start the base case at the smallest valid $n$ and adjust accordingly. The induction step still goes from $k$ to $k + 1$.