Prove results involving sums, divisibility and inequalities for all integers using the principle of mathematical induction

What this dot point is asking

NESA wants you to prove statements that hold for all integers from some starting value using mathematical induction. Extension 2 pushes well beyond simple series sums to harder divisibility results, inequalities needing an auxiliary bound, and statements where the step at $n = k + 1$ depends on more than just $n = k$, so that one base case and the usual hypothesis are not enough. The marks are concentrated in the inductive step and in choosing the right form of induction for the problem.

The structure of an induction proof

To prove that $P(n)$ holds for all integers $n \ge n_0$:

1. Base case: verify $P(n_0)$ directly.
2. Inductive hypothesis: assume $P(k)$ is true for some arbitrary integer $k \ge n_0$.
3. Inductive step: using the hypothesis, prove $P(k+1)$.
4. Conclusion: by the principle of mathematical induction, $P(n)$ holds for all integers $n \ge n_0$.

The logic is a chain. The base case starts it; the inductive step lets each true statement force the next, so truth propagates from $n_0$ to every later integer.

Induction on a series

Prove that $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$ for all integers $n \ge 1$.

Base case ($n = 1$): the left side is $1^2 = 1$; the right side is $\dfrac{1 \cdot 2 \cdot 3}{6} = 1$. Equal, so $P(1)$ holds.

Inductive step: assume $\displaystyle\sum_{r=1}^{k} r^2 = \dfrac{k(k+1)(2k+1)}{6}$. Then

The bracket is $2k^2 + 7k + 6 = (k+2)(2k+3)$, so

which is exactly the formula with $n = k+1$. The result follows by induction.

Induction on divisibility

Prove that $7^n - 1$ is divisible by $6$ for all integers $n \ge 1$.

Base case ($n = 1$): $7^1 - 1 = 6$, which is divisible by $6$.

Inductive step: assume $7^k - 1 = 6M$ for some integer $M$, so $7^k = 6M + 1$. Then

Since $7M + 1$ is an integer, $7^{k+1} - 1$ is divisible by $6$. The result follows by induction.

For a divisibility result, the reliable tactic is to write the hypothesis as an equation $f(k) = dM$, then express $f(k + 1)$ in terms of $f(k)$ so the assumption substitutes in, leaving an expression that is visibly a multiple of $d$. Adding and subtracting a convenient multiple of $f(k)$ is often the move that exposes the factor of $d$.

Induction on inequalities

Prove that $2^n > n^2$ for all integers $n \ge 5$.

Base case ($n = 5$): $2^5 = 32$ and $5^2 = 25$, and $32 > 25$, so $P(5)$ holds.

Inductive step: assume $2^k > k^2$ for some $k \ge 5$. Then $2^{k+1} = 2 \cdot 2^k > 2k^2$. It suffices to show $2k^2 \ge (k+1)^2$ for $k \ge 5$. Now

and for $k \ge 5$ this is $(k-1)^2 - 2 \ge 16 - 2 = 14 > 0$. Hence $2^{k+1} > 2k^2 \ge (k+1)^2$, completing the step.

The pattern for inequalities is a two-step chain: use the hypothesis to bound the $k + 1$ expression, then strengthen with a separate algebra inequality (rearranged to "$\ge 0$" and checked over the range) to reach the target. A single substitution is never enough, which is why so many inequality questions come in two parts: part (i) proves the helper inequality, part (ii) feeds it into the step.

Strong induction and multiple base cases

Ordinary induction lets the step use only the immediately preceding case $P(k)$. But some statements at $n = k + 1$ genuinely depend on several earlier cases. The fix is strong induction: in the step you assume $P(j)$ is true for every $j$ with $n_0 \le j \le k$, not just $j = k$, and you supply as many base cases as the recurrence reaches back.

The signpost is a recurrence (or argument) that refers to more than one earlier term. A two-term recurrence such as $a_{n} = 5a_{n-1} - 6a_{n-2}$ uses both $a_{n-1}$ and $a_{n-2}$, so to compute $a_{k+1}$ you need both $P(k)$ and $P(k-1)$ available, and you must verify two base cases ($n = 1$ and $n = 2$) so that the very first inductive step has both predecessors to stand on. Skip a base case and the chain has a broken link near the start, even if the algebra of the step is perfect.

A second classic use is structural rather than a sequence: "every integer $n \ge 2$ can be written as a product of primes." Here, when $n$ is composite you write $n = ab$ with $2 \le a, b < n$, and you need the result for both $a$ and $b$, which are smaller than $n$ but not necessarily equal to $n - 1$. Only strong induction, assuming the claim for all integers from $2$ up to $k$, lets you invoke it for $a$ and $b$.

Induction in less obvious settings

Not every induction is a sum, a divisibility, or a clean inequality. The same machinery proves:

• Closed forms for recurrences: given $a_1$ and a rule $a_{n+1} = f(a_n)$, prove a direct formula $a_n = g(n)$. The engine of the step is the recurrence, not algebraic simplification.
• Properties preserved by a process: some feature holds after each step of an iteration (for example, a quantity stays an integer, or stays positive, at every stage).
• Statements proved by going down, not up. Occasionally it is cleaner to assume the result fails and take a smallest counterexample, then construct a smaller one, a contradiction. This "least counterexample" argument is logically equivalent to strong induction and is sometimes the neatest route.

In every case the four-part skeleton survives; what changes is what powers the step.

Choosing and verifying the base case

The base case must be the smallest value of $n$ for which the statement is claimed, not a habitual $n = 1$. If the result only holds from $n = 5$, then $P(5)$ is the base case and earlier values may genuinely be false. Verify it by direct calculation of both sides and state clearly that the inequality or equality holds. A correct inductive step with the wrong base case proves nothing, because the chain of implications has no valid starting link. For strong induction, "the base case" becomes "the base cases": supply one for each term the recurrence reaches back to.

Where ordinary induction fails

It is worth knowing the ways an inductive argument can be invalid even when it looks convincing:

• The step secretly needs an earlier case. If proving $P(k + 1)$ used $P(k - 1)$ but you only assumed $P(k)$, the step is unjustified; switch to strong induction and add the missing base case.
• Too few base cases for the recurrence. A two-term recurrence with only one base case leaves the second term unproved, so the chain never gets going.
• The hypothesis is not actually used. If your step would work without assuming $P(k)$, you have a direct proof, not an induction, and more often a hidden gap.
• An induction "proof" of a false statement. The notorious "all horses are the same colour" argument fails precisely because its step from $k = 1$ to $k = 2$ relies on an overlap of two groups that does not exist; the lesson is that the step must hold for every $k \ge n_0$, including the very first, with no special small cases quietly assumed.
• Strengthening needed but missing (inequalities). Using the hypothesis gives a bound, not the target; without the separate strengthening inequality the step is incomplete.

How exam questions ask about induction

• "Prove by mathematical induction that $\sum \dots = \dots$": a series identity; split off the last term, substitute the hypothesis, simplify to the $k + 1$ form.
• "Prove that $E(n)$ is divisible by $d$": write the hypothesis as $E(k) = dM$ and finish the step with an explicit factor of $d$.
• "Prove that $E(n) > F(n)$ for $n \ge n_0$": use-then-strengthen; verify the strengthening inequality over the range.
• "A sequence is defined by $a_1 = \dots$, $a_{n} = \dots a_{n-1} \dots a_{n-2}$. Prove that $a_n = \dots$": a two-term recurrence; this is strong induction with two base cases.
• "Show that every integer $n \ge 2$ is a product of primes": strong induction, assuming the claim for all smaller integers.
• "(i) Show ... (ii) Hence prove by induction ...": part (i) is the helper you must invoke by name inside the step of part (ii).

Edge cases and what-ifs

• How many base cases? Match the number of base cases to how far the recurrence reaches back: a two-term recurrence needs two, a three-term recurrence needs three. Verify each by direct substitution.
• Strong versus ordinary. If the step at $k + 1$ only ever uses $P(k)$, ordinary induction suffices. Reach for strong induction exactly when the step needs earlier cases (a multi-term recurrence, or splitting $n = ab$ into smaller factors).
• Base case not at $n = 1$. When the claim starts at $n = 0$, $n = 2$ or higher, the base case (or cases) sit there. Everything else is unchanged.
• Strengthening fails near the threshold. For an inequality, the helper inequality sometimes only holds from a slightly larger $k$ than the base case; if so, raise the base case to where both the base check and the strengthening hold.
• A least-counterexample alternative. A strong induction can always be recast as "suppose the smallest failing $n$ exists, then build a smaller one"; use whichever the question's structure makes cleaner.