Mathematical induction for inequalities: the technique and the algebraic care

What this dot point is asking

NESA wants you to use mathematical induction to prove that an inequality involving an integer parameter $n$ holds for every $n$ from some starting value onward. The four-part skeleton is identical to a series proof, but the inductive step is harder, because an inequality only gives you a bound, not an equation, so you cannot simply substitute and simplify. Instead you use the hypothesis to take one step, and then you have to close the gap to the target with a second, separate inequality. Getting that second step right, and checking it actually holds for your range of $n$, is where the marks live.

The answer

The four-part structure

The structure is the same template as every induction, adapted to an inequality $E(n) \le F(n)$ (or strict, or reversed) for all $n \ge n_0$:

1. Base case: verify the inequality directly at $n = n_0$, evaluating both sides.
2. Inductive hypothesis: assume the inequality holds at $n = k$ (for some $k \ge n_0$).
3. Inductive step: use the hypothesis to derive the inequality at $n = k + 1$.
4. Conclusion: by the principle of mathematical induction, the inequality holds for all $n \ge n_0$.

The use-then-strengthen two-step (the core technique)

The technique that makes inductive steps for inequalities work is a two-step chain: use the hypothesis to bound the $k + 1$ expression, then strengthen that bound until it reaches the target. Concretely, to prove $\text{LHS}(k + 1) > \text{RHS}(k + 1)$:

1. Use the hypothesis. Rewrite $\text{LHS}(k + 1)$ in terms of $\text{LHS}(k)$ (for example $2^{k + 1} = 2 \cdot 2^k$), then replace $\text{LHS}(k)$ by the bound the hypothesis gives. This produces an intermediate expression $G$ with $\text{LHS}(k + 1) > G$.
2. Strengthen to the target. Show separately that $G \ge \text{RHS}(k + 1)$. This is a pure algebra inequality with no induction in it; you usually rearrange it to "something $\ge 0$" and verify that for all $k \ge n_0$.

Chaining the two gives $\text{LHS}(k + 1) > G \ge \text{RHS}(k + 1)$, hence $\text{LHS}(k + 1) > \text{RHS}(k + 1)$. The art is choosing the intermediate $G$ so that both links hold; usually $G$ is "the hypothesis bound, scaled up the same way the LHS was".

The growth-comparison view

A useful way to see why the step works is to compare how fast each side grows. Write $\text{LHS}(k + 1) = \text{LHS}(k) + \Delta_{\text{L}}$ and $\text{RHS}(k + 1) = \text{RHS}(k) + \Delta_{\text{R}}$, where the $\Delta$s are the increments. The hypothesis says $\text{LHS}(k) \ge \text{RHS}(k)$. If you can show the left side grows at least as fast, $\Delta_{\text{L}} \ge \Delta_{\text{R}}$, then adding the two inequalities gives $\text{LHS}(k + 1) \ge \text{RHS}(k + 1)$. For an exponential-versus-polynomial inequality the left side eventually grows much faster, which is exactly why the inequality holds once $n$ is large enough, and why these statements usually start at $n = 4$ or $n = 5$ rather than $n = 1$.

Choosing the right base case

Many inequalities are simply false for small $n$ and only become true past a threshold. The base case must be the smallest value for which the claim is asserted, so always check the stated range. For $2^n > n^2$ the inequality fails at $n = 2, 3, 4$ (for instance $2^4 = 16 < 16 = 4^2$ is not strict, and $2^3 = 8 < 9$) and first holds at $n = 5$, which is why the question says $n \ge 5$. Start the base case there.

Common patterns

• Exponential beats polynomial: $2^n > n^2$ for $n \ge 5$, $3^n > n^3$ for $n \ge 4$. Step the exponential up by its base, then strengthen.
• Factorial beats exponential: $n! > 2^n$ for $n \ge 4$. Stepping up multiplies the factorial by $(k + 1)$, which quickly dominates the doubling.
• Sum or product inequalities: bounds on a running sum of fractions, or on a product. Split off the last term (as for series), apply the hypothesis, then strengthen.

A note on direction and strictness

Inequalities are fragile under algebra in a way equations are not. Multiplying both sides by a quantity preserves the direction only if that quantity is positive; multiply by a negative and the inequality flips. And a strict inequality ($>$) does not automatically survive: if every step uses $\ge$, you only get $\ge$ at the end. To keep strictness, make sure at least one link in the chain is genuinely strict (the "use" link is strict whenever the hypothesis is strict and you scale by a positive factor).

How exam questions ask about inequalities

• "Prove by mathematical induction that $E(n) > F(n)$ for $n \ge n_0$": the standard wording. The given $n_0$ is your base case.
• "Prove that $2^n > n^2$ for all integers $n \ge 5$": a named exponential-versus-polynomial inequality. Step up the exponential, then strengthen with a quadratic-positivity argument.
• "Show that $n! > 2^n$ for $n \ge 4$": factorial versus exponential; the step multiplies by $(k + 1)$.
• "Prove $\sum_{i = 1}^{n} \frac{1}{i^2} \le 2 - \frac{1}{n}$": a sum bound. Split off the last term, apply the hypothesis, then verify the remaining inequality.
• "For what values of $n$ is $E(n) > F(n)$? Prove your answer.": test small $n$ to find the threshold $n_0$, then prove it by induction from $n_0$.

Edge cases and what-ifs

• Finding the threshold yourself. If the question does not give $n_0$, test small values until the inequality first holds, then prove it from there. State clearly which is the base case.
• Non-strict base, strict elsewhere. A base case can be an equality (as in the sum inequality at $n = 1$, where both sides equal $1$). A $\le$ claim is satisfied by equality, so that is fine; you only need strictness when the claim itself is strict.
• The strengthening inequality fails near the threshold. Sometimes the pure-algebra inequality only holds from a slightly larger $k$ than the base case. If so, the base case must be raised to where both the base check and the strengthening hold. Always confirm the threshold of the strengthening step.
• Reversed inequalities. For a "$\le$" or "$<$" claim the method is the mirror image: bound above instead of below. The two-step chain still applies, with the inequalities pointing the other way.