NSWMaths Extension 1Syllabus dot point

How do we use induction to prove an inequality holds for every positive integer?

Prove inequalities involving an integer parameter $n$ using mathematical induction

A focused answer to the HSC Maths Extension 1 dot point on induction for inequalities. The standard structure, the trick of strengthening one side to match the hypothesis, and worked examples including $2^n > n^2$ and $n! > 2^n$ .

Generated by Claude OpusReviewed by Better Tuition Academy7 min answerUpdated 2026-05-20

Have a quick question? Jump to the Q&A page

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 positive integer (or for $n \ge n_0$ ). The structure is the same as for series, but the algebra is often more delicate.

The answer

The structure

To prove $E(n) \le F(n)$ (or strict, or reversed) for all $n \ge n_0$ :

Base case: Verify the inequality directly at $n = n_0$ .
Inductive hypothesis: Assume the inequality holds at $n = k$ .
Inductive step: Use the hypothesis to derive the inequality at $n = k + 1$ .
Conclusion: By the principle of mathematical induction, the inequality holds for all $n \ge n_0$ .

The strategy in the step

The standard technique is to show that, going from $n = k$ to $n = k + 1$ , the "growth" of one side is at least as much as the "growth" of the other.

For $E(k + 1) \ge F(k + 1)$ , write $E(k + 1) = E(k) + \Delta_E$ and $F(k + 1) = F(k) + \Delta_F$ . The hypothesis says $E(k) \ge F(k)$ . If you can show $\Delta_E \ge \Delta_F$ , adding the inequalities gives the result.

Alternatively, manipulate $E(k + 1)$ algebraically and use the hypothesis to bound it.

Starting at IMATH_18

Many inequalities are only true for $n \ge$ some threshold. Set the base case at that threshold.

For $2^n > n^2$ for $n \ge 5$ : base case is $n = 5$ , hypothesis assumes the inequality at $n = k \ge 5$ , step shows it at $k + 1$ .

Common patterns

Geometric versus polynomial. $2^n > n^2$ for $n \ge 5$ , $3^n > n^3$ for $n \ge 4$ , etc.
Factorial versus exponential. $n! > 2^n$ for $n \ge 4$ .
Sums and products. Show some inequality on a sum-of-fractions or product structure.

Algebraic care

Inequalities require you to be careful about the direction of the inequality when you multiply by a quantity. Always check whether the multiplier is positive (preserves direction) or negative (reverses).

For strict inequalities, the step often requires a strict inequality on $\Delta_E > \Delta_F$ .

Worked example

Exponential beats polynomial

Prove $2^n > n^2$ for $n \ge 5$ .

Base ( $n = 5$ ): IMATH_3 , $5^2 = 25$ . $32 > 25$ . Holds.
Hypothesis: Assume $2^k > k^2$ for some $k \ge 5$ .
Step: Show $2^{k + 1} > (k + 1)^2$ .

$2^{k + 1} = 2 \cdot 2^k > 2 k^2$ by the hypothesis.

We need $2 k^2 \ge (k + 1)^2 = k^2 + 2 k + 1$ , that is $k^2 - 2 k - 1 \ge 0$ , that is $k \ge 1 + \sqrt{2} \approx 2.41$ .

Since $k \ge 5 > 2.41$ , this holds, and so $2 k^2 \ge (k + 1)^2$ .

Therefore $2^{k + 1} > 2 k^2 \ge (k + 1)^2$ .

Conclusion: By induction, $2^n > n^2$ for all $n \ge 5$ .

Factorial versus exponential

Prove $n! > 2^n$ for $n \ge 4$ .

Base ( $n = 4$ ): IMATH_21 , $2^4 = 16$ . $24 > 16$ . Holds.
Hypothesis: Assume $k! > 2^k$ for some $k \ge 4$ .
Step: IMATH_26 by hypothesis.

We need $(k + 1) \cdot 2^k \ge 2^{k + 1} = 2 \cdot 2^k$ , that is $k + 1 \ge 2$ , i.e. $k \ge 1$ . Since $k \ge 4$ , true.

So $(k + 1)! > 2^{k + 1}$ .

Conclusion: By induction, $n! > 2^n$ for all $n \ge 4$ .

Sum inequality

Prove $\sum_{i = 1}^{n} \frac{1}{i^2} \le 2 - \frac{1}{n}$ for all positive integers $n$ .

Base ( $n = 1$ ): LHS $= 1$ , RHS $= 2 - 1 = 1$ . Equal, so $\le$ holds.
Hypothesis: IMATH_40 .
Step: IMATH_41 by the hypothesis.

We need this to be $\le 2 - \frac{1}{k + 1}$ .

Equivalent: $-\frac{1}{k} + \frac{1}{(k + 1)^2} \le -\frac{1}{k + 1}$ , that is $\frac{1}{k + 1} - \frac{1}{k} \le -\frac{1}{(k + 1)^2}$ , that is $\frac{k - (k + 1)}{k(k + 1)} = -\frac{1}{k(k + 1)} \le -\frac{1}{(k + 1)^2}$ .

Multiplying by $-1$ and flipping: $\frac{1}{k(k + 1)} \ge \frac{1}{(k + 1)^2}$ , which holds iff $(k + 1)^2 \ge k(k + 1)$ , that is $k + 1 \ge k$ . True.

Conclusion: By induction, the inequality holds for all positive integers $n$ .

A simple double

Prove $2^n \ge n + 1$ for all positive integers $n$ .

Base ( $n = 1$ ): IMATH_54 . Holds.
Hypothesis: IMATH_55 .
Step: IMATH_56 (since $k \ge 1$ , $2 k + 2 \ge k + 2$ ).

So $2^{k + 1} \ge (k + 1) + 1$ .

Conclusion: By induction, the inequality holds for all positive integers.