Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 37 · Getting Started

Induction and Inequalities

Prove statements for all natural numbers with induction, and meet Bernoulli's inequality, the triangle inequality and AM-GM, workhorses of analysis.

Many facts in analysis hold "for every natural number n": a sequence bound, a formula for a partial sum, an estimate. Mathematical induction proves all of them with two finite steps. Together with a handful of standard inequalities, it gives you most of the working tools you need before we study the real numbers themselves.

The principle of induction

Let P(n) be a statement about the natural number n. If

  1. Base case: P(1) is true, and
  2. Inductive step: whenever P(k) is true, P(k + 1) is true,

then P(n) is true for all n ∈ ℕ. Think of dominoes: the first falls, and each falling domino knocks over the next.

Example. Prove 1 + 2 + ... + n = n(n + 1)/2.

Base case. For n = 1: left side is 1, right side is 1·2/2 = 1. ✓

Inductive step. Assume 1 + ... + k = k(k + 1)/2. Then

1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2,

which is the formula for n = k + 1. ∎

Python Check a formula before proving it

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second experiment is a warning: a pattern that holds for the first 40 cases can still fail. Induction, not examples, gives certainty.

Strong induction

Sometimes you need more than P(k). Strong induction assumes P(1), ..., P(k) all hold and proves P(k + 1). It is equivalent in power to ordinary induction. It is the natural tool for statements like "every integer ≥ 2 is a product of primes".

Bernoulli's inequality

Claim. For real x ≥ -1 and integer n ≥ 1: (1 + x)ⁿ ≥ 1 + nx.

Proof by induction. For n = 1 both sides equal 1 + x. Assume it for k. Since 1 + x ≥ 0, multiply both sides of (1 + x)^k ≥ 1 + kx by 1 + x:

(1 + x)^{k+1} ≥ (1 + kx)(1 + x) = 1 + (k + 1)x + kx² ≥ 1 + (k + 1)x,

because kx² ≥ 0. ∎

Bernoulli's inequality will show up when proving that rⁿ → 0 for |r| < 1 and when studying the number e.

Python Bernoulli's inequality numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The triangle inequality

For real numbers a, b:

|a + b| ≤ |a| + |b|.

Proof. We have -|a| ≤ a ≤ |a| and -|b| ≤ b ≤ |b|. Add: -(|a| + |b|) ≤ a + b ≤ |a| + |b|, which says |a + b| ≤ |a| + |b|. ∎

The reverse triangle inequality | |a| - |b| | ≤ |a - b| follows by applying the first to a = (a - b) + b. Almost every ε-proof ends with a triangle inequality: "distance from x to z is at most distance from x to y plus y to z".

AM-GM inequality

For a, b ≥ 0: √(ab) ≤ (a + b)/2.

Proof. (√a - √b)² ≥ 0 expands to a - 2√(ab) + b ≥ 0. Rearranging gives the claim, with equality exactly when a = b. ∎

The general version for n numbers: the geometric mean never exceeds the arithmetic mean.

To prove an inequality A ≤ B, try showing B - A is a sum of squares or a product of nonnegative factors. It is the same trick as in the AM-GM proof above.

flowchart LR
  A["Base case P(1)"] --> B["Assume P(k)"]
  B --> C["Prove P(k+1)"]
  C --> D["P(n) for all n"]

Induction: a base case plus a step that passes truth from k to k + 1.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What two parts does an induction proof need?

    Prove P(1), then show P(k) implies P(k+1).
  2. 2. What does Bernoulli's inequality say for x ≥ -1 and integer n ≥ 1?

    Expanding the power gives extra nonnegative terms beyond 1 + nx, so the power is at least 1 + nx.
  3. 3. The triangle inequality for reals states

    The absolute value of a sum is at most the sum of absolute values; equality holds when a and b have the same sign.
  4. 4. Why is checking n = 1 to 40 not enough to prove a claim for all n?

    n² + n + 41 is prime for n = 0 to 39 but 40² + 40 + 41 = 1681 = 41², which is not prime.

Summary

  • Induction proves P(n) for all n from a base case and a step P(k) ⇒ P(k + 1).
  • Strong induction assumes all earlier cases.
  • Bernoulli: (1 + x)ⁿ ≥ 1 + nx for x ≥ -1.
  • Triangle inequality: |a + b| ≤ |a| + |b|; AM-GM: √(ab) ≤ (a + b)/2.
  • Examples build confidence but only proofs settle "for all".

Next: The Ordered Field Axioms