Recognition: Inequality Induction Proofs Need the Hypothesis Plus One Extra Inequality — Plan for the Gap

A student who has proved several identity-style induction problems — "1 + 2 + \dots + n = \frac{n(n+1)}{2}" and its cousins — meets their first inequality-style problem and feels an unfamiliar stickiness. The hypothesis lands them in the right neighbourhood, but not exactly at the goal. Something is left over, and the hypothesis alone cannot finish the step.

This is not a bug in the approach. It is the shape of every inequality induction problem. For inequalities, the inductive hypothesis gets you close, but you almost always need one extra inequality to bridge the remaining gap. Recognising this in advance is the difference between getting stuck and planning for the bridge.

The pattern

Identity proofs. When the goal is "\text{LHS}(n) = \text{RHS}(n)," the inductive step usually goes:

\text{LHS}(k+1) = \text{LHS}(k) + \text{new term} = \text{RHS}(k) + \text{new term} = \text{RHS}(k+1)

Each "=" is an algebraic identity. The hypothesis plugs in cleanly, and the remaining algebra is pure computation.

Inequality proofs. When the goal is "\text{LHS}(n) \geq \text{RHS}(n)" (or >, \leq, <), the inductive step typically looks like:

\text{LHS}(k+1) = \text{LHS}(k) \cdot \text{something} \geq \text{RHS}(k) \cdot \text{something} \quad \text{(by hypothesis)}

Now you have \text{RHS}(k) \cdot \text{something}, but your goal is to show this is \geq \text{RHS}(k+1). That last step — \text{RHS}(k) \cdot \text{something} \geq \text{RHS}(k+1) — is a separate inequality, independent of the hypothesis. It is the "gap" you must plan for.

This extra inequality is always there. Expect it. Hunt for it the moment you start the inductive step.

A worked example that shows the gap

Problem. Prove 2^n > n^2 for all n \geq 5.

Base case. n = 5: 2^5 = 32, 5^2 = 25, 32 > 25. \checkmark

Inductive hypothesis. Assume 2^k > k^2 for some k \geq 5.

Goal. Prove 2^{k+1} > (k+1)^2.

Inductive step — use the hypothesis.

2^{k+1} = 2 \cdot 2^k > 2 \cdot k^2 \quad \text{(by hypothesis)}.

So 2^{k+1} > 2 k^2. But the goal is 2^{k+1} > (k+1)^2 = k^2 + 2k + 1. The hypothesis landed us at 2 k^2; the goal is k^2 + 2k + 1. There is a gap.

Inductive step — bridge the gap.

The gap: we have 2^{k+1} > 2 k^2; we need 2^{k+1} > k^2 + 2k + 1. It suffices to show

2 k^2 \geq k^2 + 2k + 1, \quad \text{i.e., } k^2 - 2k - 1 \geq 0, \quad \text{i.e., } k^2 \geq 2k + 1.

Is k^2 \geq 2k + 1 true for k \geq 5? At k = 5: 25 \geq 11, yes. For k \geq 5, k^2 - 2k = k(k-2) \geq 5 \cdot 3 = 15 > 1, so k^2 \geq 2k + 1 holds. \checkmark

Combining:

2^{k+1} > 2 k^2 \geq k^2 + 2k + 1 = (k+1)^2.

By induction, 2^n > n^2 for all n \geq 5.

Notice what just happened. The hypothesis took us from 2^{k+1} = 2 \cdot 2^k to 2 \cdot k^2 — one step. Then we needed a completely separate inequality (2 k^2 \geq (k+1)^2, which simplifies to k^2 \geq 2k + 1) to finish. That second inequality had nothing to do with induction; it was a standalone algebraic fact about k. Without planning for this extra inequality, the proof gets stuck after the first step.

Why the gap is structural, not a mistake

Consider the shape of "f(n) \geq g(n)." Going from k to k+1, both sides change:

LHS changes from f(k) to f(k+1).
RHS changes from g(k) to g(k+1).

The hypothesis tells you f(k) \geq g(k). The goal is f(k+1) \geq g(k+1). To bridge them, you need to track how both sides change and how their growth rates compare.

If f grows faster than g — say f(k+1) \geq c \cdot f(k) and g(k+1) \leq c \cdot g(k) for some c > 0 — then f(k+1) \geq c f(k) \geq c g(k) \geq g(k+1), and you are done with no extra work. But usually the growth rates are not cleanly comparable, and you must explicitly bound one in terms of the other. That bound is the extra inequality.

Why identity proofs do not have this gap: in an identity, both sides change by the same increment between k and k+1. \text{LHS}(k+1) - \text{LHS}(k) = \text{RHS}(k+1) - \text{RHS}(k). Substituting the hypothesis finishes immediately. Inequalities do not share this structure — the two sides can change by different amounts, and the "rate difference" is what the extra inequality bounds.

A visual: the gap you plan for

Three curves for $n \geq 5$: $2^n$ (the true LHS), $2 k^2$ (where the inductive hypothesis lands the LHS after multiplying by $2$), and $(k+1)^2$ (the RHS of the goal). The hypothesis carries you to the red dashed curve; the green curve is your target. The extra inequality $2 k^2 \geq (k+1)^2$ is the bound you need to close the red-to-green gap. Drag $k$ to see the gap between the red and green curves.

A practical planning template for inequality induction

Before you start manipulating symbols, sketch:

What does the hypothesis give me? Write \text{LHS}(k) \geq \text{RHS}(k) and think about the most natural way to use it.
What is the goal asking for? Write \text{LHS}(k+1) \geq \text{RHS}(k+1) explicitly (this is also the standard habit from Write P(k+1) Explicitly).
How is LHS(k+1) related to LHS(k)? Usually LHS(k+1) = LHS(k) \cdot c or LHS(k) + c for some c. Apply the hypothesis to this expression.
What is the remaining gap? After step 3, you have an inequality of the form "LHS(k+1) \geq something." Compare "something" to RHS(k+1) — the difference is the gap.
What inequality bridges the gap? This is the extra inequality. Often it is a simple polynomial or exponential fact about k that holds for k \geq n_0.

This template works for 2^n > n^2, n! > 2^n for n \geq 4, (1 + x)^n \geq 1 + nx (Bernoulli), and many competition inequalities. Internalise the pattern, and the inductive step becomes a fill-in-the-blank exercise.

When the extra inequality fails

If the gap turns out to be impossible to bridge — the inequality you need is simply not true for the range of k you have — one of two things is happening:

You need a bigger base case. The extra inequality might fail for small k but hold for large k. Bump the base case to where the extra inequality starts working, and verify the original claim directly up to that point. For example, the gap inequality 2 k^2 \geq (k+1)^2 simplifies to k^2 \geq 2k + 1, which holds for k \geq 3 (check: 9 \geq 7, 16 \geq 9, 25 \geq 11, ...). That is why the base case for 2^n > n^2 is n = 5 — it is chosen to make the gap bridgeable from there onward. (See Match Base Case to Inductive Step Threshold.)

You need to strengthen the hypothesis. Sometimes the problem as stated has a hypothesis that is too weak to bridge the gap. You prove a stronger statement Q(n) that implies P(n) — stronger statements can have stronger hypotheses. This is called "strengthening the inductive hypothesis" and is a classic competition trick. The counter-intuitive fix: making the thing you prove harder makes the proof easier.

A second worked example

Problem. Prove n! > 2^n for all n \geq 4.

Base case. n = 4: 24 > 16. \checkmark

Hypothesis. k! > 2^k for some k \geq 4.

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

Inductive step.

(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k \quad \text{(by hypothesis)}.

Now the gap: we have (k+1)! > (k+1) \cdot 2^k; we need (k+1)! > 2 \cdot 2^k = 2^{k+1}. Extra inequality required: (k+1) \cdot 2^k \geq 2 \cdot 2^k, i.e., k + 1 \geq 2, i.e., k \geq 1. True for all k \geq 4. \checkmark

\text{Therefore } (k+1)! > (k+1) \cdot 2^k \geq 2 \cdot 2^k = 2^{k+1}.

By induction, n! > 2^n for all n \geq 4.

Notice the gap was simpler here — just k + 1 \geq 2. But it was still structurally separate from the hypothesis. The hypothesis gave k! > 2^k; the extra inequality said k + 1 \geq 2. Two independent facts, combined to finish.

Spotting the gap in a Bernoulli-style problem

Problem. Prove (1 + x)^n \geq 1 + nx for all n \geq 1 and all x \geq -1 (Bernoulli's inequality).

Base case. n = 1: 1 + x \geq 1 + x. \checkmark

Hypothesis. (1 + x)^k \geq 1 + kx for some k \geq 1.

Goal. (1 + x)^{k+1} \geq 1 + (k+1)x.

Inductive step.

(1 + x)^{k+1} = (1 + x)(1 + x)^k \geq (1 + x)(1 + kx) \quad \text{(by hypothesis, using } 1 + x \geq 0\text{)}.

Expanding: (1 + x)(1 + kx) = 1 + kx + x + kx^2 = 1 + (k+1)x + kx^2.

Now the gap: we have (1+x)^{k+1} \geq 1 + (k+1)x + kx^2; we need (1+x)^{k+1} \geq 1 + (k+1)x. Extra inequality: 1 + (k+1)x + kx^2 \geq 1 + (k+1)x, i.e., k x^2 \geq 0. True for all x \in \mathbb{R} and k \geq 1. \checkmark

\text{Therefore } (1+x)^{k+1} \geq 1 + (k+1)x + kx^2 \geq 1 + (k+1)x.

By induction, (1 + x)^n \geq 1 + nx for n \geq 1, x \geq -1.

Lesson. The gap was k x^2 \geq 0 — an utterly simple inequality, yet it was logically separate from the hypothesis. The hypothesis said "(1+x)^k \geq 1 + kx"; the extra inequality said "squares are non-negative." Two independent facts. Planning for the gap in advance turns this proof from "where do I go after applying the hypothesis?" into "oh, I just need kx^2 \geq 0 — done."

Notice also the subtle use of "1 + x \geq 0" when multiplying both sides of the hypothesis by (1 + x). That is a third required fact, beyond the hypothesis and the kx^2 \geq 0 bound. Inequality induction often has this layered structure.

The one-line takeaway

In induction proofs of inequalities, expect the inductive hypothesis to land you close to the goal but not at it. There is almost always a separate, extra inequality required to bridge the remaining gap. Plan for this gap in advance: identify what the hypothesis gives you, what the goal requires, and what bound connects them.

Inequality induction is identity induction with one more moving part. Once you internalise the extra-inequality pattern, the added complexity becomes routine.