Course contentsShow
← Computer Science
Lesson 92 of 2,8722. Discrete Mathematics for CSFree lesson

Inequality Proofs by Induction

Proving inequalities like 2^n > n² for sufficiently large n using the inductive framework.

Inequality Proofs by Induction

You'll learn how to prove that one expression stays larger (or smaller) than another for all sufficiently large integers using induction.

The Core Idea

Some inequalities aren't equalities—they claim one side is always bigger than the other once you pass a certain starting point. For example, "2^n > n² for all n ≥ 5" says exponential growth beats quadratic growth eventually. Induction is perfect for proving these claims systematically.

The Structure

Just like summing series or divisibility proofs, inequality proofs follow the three-step induction framework:

  1. Base Case: Verify the inequality holds at the starting value (often called n₀). For 2^n > n², check n = 5: is 2⁵ > 5²? Yes, 32 > 25 ✓

  2. Inductive Hypothesis: Assume the inequality is true for some arbitrary k ≥ n₀. So assume 2^k > k².

  3. Inductive Step: Prove it holds for k+1. You need to show 2^(k+1) > (k+1)².

The Key Technique

Start with what you know (2^k > k²) and transform it toward what you need. For our example:

  • 2^(k+1) = 2 · 2^k
  • By hypothesis, 2^k > k², so 2^(k+1) > 2k²
  • Now show 2k² > (k+1)² when k ≥ 5
  • Expanding: 2k² > k² + 2k + 1 simplifies to k² > 2k + 1
  • This is true for k ≥ 5 ✓

The inequality "chains together," letting you bridge from the assumption to the conclusion.

Why It Matters

Algorithm analysis constantly compares growth rates. Proving one function dominates another tells you which algorithm scales better as input size grows—critical for choosing efficient solutions.

Key Takeaway: Inequality proofs by induction follow the same base-hypothesis-step pattern, but you manipulate inequalities (preserving the < or > direction) to show each case implies the next, often for all n beyond some threshold.