Proof by Induction — Inequalities

Key Terms

Inequality induction: Prove P(n): f(n) > g(n) (or ≥) for all n ≥ n₀ using induction.
Base case: Check the base case by direct substitution; choose n₀ carefully (often n₀ ≥ 2 or n₀ ≥ 4).
Inductive hypothesis: Assume f(k) > g(k) for some k ≥ n₀.
Inductive step: Show f(k+1) > g(k+1); typically by multiplying f(k) > g(k) by a positive quantity or using bounding.
Bounding argument: If f(k+1) ≥ f(k) + something > g(k) + something ≥ g(k+1), the inequality is established.
Strict vs non-strict: Use > for strict inequalities and ≥ for non-strict; the four steps are the same but the conclusion changes.

Inequality Induction Strategy

The four-step structure applies, but the inductive step uses inequality algebra:

Step 1 — Base case: Verify the inequality holds for the first value of n.

Step 2 — Hypothesis: Assume P(k) is true: f(k) [inequality] g(k).

Step 3 — Inductive step: Prove P(k+1) by:

(i) Starting with f(k+1) and expressing it in terms of f(k)

(ii) Substituting the inductive hypothesis to replace f(k)

(iii) Showing the remaining terms preserve the inequality direction

Step 4 — Conclusion: By PMI, the result holds for all n ≥ [starting value].

Key technique: If f(k+1) = f(k) + [extra terms], and f(k) ≥ g(k) by hypothesis, then showing [extra terms] makes f(k+1) ≥ g(k+1) requires careful algebra. Never just assume the inequality — you must derive it rigorously.

Common Types of Inequality Proofs

Exponential beats linear: 2ⁿ > n • 3ⁿ ≥ 2n+1

Factorial beats exponential: n! > 2ⁿ for n ≥ 4 • n! ≥ 2ⁿ⁻¹

Quadratic vs exponential: 2ⁿ ≥ n² for n ≥ 4

Bernoulli's inequality: (1+x)ⁿ ≥ 1+nx for x ≥ 0 — key inequality in analysis

Algebraic: n² ≥ 2n−1

Worked Example 1 — Prove 2ⁿ > n for all n ≥ 1

Step 1 — Base case (n = 1):

2¹ = 2 > 1. ✓

Step 2 — Inductive hypothesis:

Assume 2^k > k for some k ≥ 1.

Step 3 — Inductive step: Show 2^k+1 > k+1.

2^k+1 = 2 × 2^k > 2k [by hypothesis, since 2^k > k implies 2 × 2^k > 2k]

And 2k = k + k ≥ k + 1 for k ≥ 1 [since k ≥ 1]

Therefore 2^k+1 > 2k ≥ k+1, so 2^k+1 > k+1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2ⁿ > n for all integers n ≥ 1.

Worked Example 2 — Prove 3ⁿ ≥ 2n+1 for all n ≥ 1

Step 1 — Base case (n = 1):

3¹ = 3 ≥ 3 = 2(1)+1. ✓

Step 2 — Inductive hypothesis:

Assume 3^k ≥ 2k+1.

Step 3 — Inductive step: Show 3^k+1 ≥ 2(k+1)+1 = 2k+3.

3^k+1 = 3 × 3^k ≥ 3(2k+1) = 6k+3 [by hypothesis]

Now check: 6k+3 ≥ 2k+3? This requires 4k ≥ 0, which is true for all k ≥ 1. ✓

Therefore 3^k+1 ≥ 6k+3 ≥ 2k+3 = 2(k+1)+1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 3ⁿ ≥ 2n+1 for all integers n ≥ 1.

Hot Tip: When using transitivity (a > b ≥ c implies a > c), make it explicit. Exam markers want to see each inequality step justified.

Why Inequality Induction is Different

In equality induction (e.g. summation formulas), the inductive step is usually mechanical: add the next term to both sides and simplify until you get the required form. The algebra is tight — there is one correct answer to reach.

Inequality induction is more flexible but also more demanding. You must preserve the direction of the inequality at every step. A common mistake is to assume what you're trying to prove, or to reverse the inequality sign accidentally.

The key pattern is the chain of inequalities: you establish something like

f(k+1) = [expression involving f(k)] ≥ [new expression] ≥ g(k+1)

Each step must be independently justified.

The “Sandwich” Technique

The most reliable method is:

Write f(k+1) in terms of f(k). (e.g. 2^k+1 = 2 × 2^k)
Apply the hypothesis to get an intermediate inequality. (e.g. 2 × 2^k > 2k)
Establish a further inequality to reach g(k+1). (e.g. 2k ≥ k+1 because k ≥ 1)
Chain them: f(k+1) > [intermediate] ≥ g(k+1), so f(k+1) > g(k+1).

Always state why each inequality holds — either “by hypothesis”, “since k ≥ 1”, or “since k² ≥ 0” etc.

Choosing the Correct Base Case

The base case must be the exact value of n stated in the claim. If you pick the wrong starting point, the proof is invalid even if every other step is correct.

Some inequalities only become true after a certain value. For example:

n! > 2ⁿ requires n ≥ 4. Check: n=3: 6 < 8 ✗. n=4: 24 > 16 ✓.
2ⁿ ≥ n² requires n ≥ 4. Check: n=3: 8 < 9 ✗. n=4: 16 = 16 ✓.
2ⁿ > n² requires n ≥ 5. Check: n=4: 16 = 16 ✗. n=5: 32 > 25 ✓.

Always verify the base case explicitly — don’t assume it holds.

A Warning: Incorrect Proofs and Paradoxes

Induction can produce convincing-looking but completely wrong proofs if the base case or inductive step is flawed. A classic example is the (false) “proof” that all positive integers are equal — the inductive step appears to work for passing from k to k+1, but the base case P(1) and P(2) fails. This illustrates why every step is essential: base case, hypothesis, step, conclusion. If any one is missing or wrong, the proof is invalid.

Factorial Inequalities

Factorials grow faster than exponentials, but only after a threshold. The key insight in the inductive step for n! > 2ⁿ is that once k ≥ 4, we have k+1 ≥ 5 > 2, so multiplying by k+1 adds more than multiplying by 2. Formally: (k+1)! = (k+1) × k! > (k+1) × 2^k ≥ 2 × 2^k = 2^k+1.

The inequality n! ≥ 2ⁿ⁻¹ is weaker and holds for all n ≥ 1 (with equality at n=1). It uses the same idea: for k+1 ≥ 2, multiplying by k+1 is at least as big as multiplying by 2.

Bernoulli’s Inequality and its Significance

Bernoulli’s inequality states: for x ≥ 0 and all integers n ≥ 1,

(1+x)ⁿ ≥ 1 + nx

This is one of the most useful elementary inequalities in mathematics. Its applications include:

Finance: Compound interest satisfies (1+r)ⁿ ≥ 1+nr, giving a lower bound on growth.
Probability: Bounds on probability products.
Analysis: Proving convergence of sequences.

The proof by induction is elegant. In the inductive step, the key observation is that after expanding (1+x)(1+kx) = 1+(k+1)x+kx², the extra term kx² is non-negative (since k ≥ 1 and x ≥ 0), so dropping it preserves the inequality: 1+(k+1)x+kx² ≥ 1+(k+1)x.

Summary of Strategy

1. Write f(k+1) = [something involving f(k)]

2. Apply the hypothesis: replace f(k) with the bound

3. Show this implies f(k+1) ≥ g(k+1) using a justified inequality

4. State clearly: “Since k ≥ [base], [auxiliary inequality] holds.”

Practice Questions

Question 1 Fluency

Prove by mathematical induction that 2ⁿ ≥ n+1 for all integers n ≥ 1.

Question 2 Fluency

Prove by mathematical induction that n! ≥ 2ⁿ⁻¹ for all integers n ≥ 1.

Question 3 Fluency

Prove by mathematical induction that n² ≥ 2n−1 for all integers n ≥ 1.

Question 4 Fluency

Prove by mathematical induction that 3ⁿ ≥ 2n+1 for all integers n ≥ 1.

Question 5 Understanding

Prove by mathematical induction that n! > 2ⁿ for all integers n ≥ 4.

Question 6 Understanding

Prove by mathematical induction that 2ⁿ ≥ n² for all integers n ≥ 4.

Question 7 Understanding

Prove by mathematical induction that (1+x)ⁿ ≥ 1+nx for all x ≥ 0 and all integers n ≥ 1. (Bernoulli’s Inequality)

Question 8 Understanding

Prove by mathematical induction that 2n+3 ≤ 2ⁿ for all integers n ≥ 4.

Question 9 Problem Solving

Prove by mathematical induction that 2ⁿ > n² for all integers n ≥ 5.

Question 10 Problem Solving

Prove by mathematical induction that

&frac11;² + ½² + ⅓² + … + ¹⁄_n² ≤ 2 − ¹⁄_n

for all integers n ≥ 1. (That is, the sum ∑_k=1ⁿ 1/k² ≤ 2 − 1/n.)

See Answers ➔