Inequality Induction
A geometric series grows linearly in $n$; an exponential grows exponentially. Eventually the exponential wins — but proving "eventually" rigorously requires a careful induction on an inequality. Unlike sum identities (where LHS = RHS at the end), here you must show LHS for $k+1$ is at least the RHS for $k+1$. This lesson teaches the moves: $2^n > n$, $n! > 2^n$, Bernoulli's $(1+x)^n \geq 1+nx$.
You want to prove $2^n > n$ for all $n \geq 1$. Before reading on — what does the inductive step need to show? Specifically, given $2^k > k$ (the IH), how would you bound $2^{k+1}$ from below and show it exceeds $k+1$? Sketch your reasoning.
Every inequality induction rewards two habits: apply the IH to bound LHS$_{k+1}$ from below, then close the gap with a small auxiliary inequality (often $k \geq 1$, $k \geq 4$, or $1 + x > 0$). Inequality proofs are about chains of $\geq$ that all point the right way.
The bound-and-close strategy: (1) express $\text{LHS}_{k+1}$ in terms of $\text{LHS}_k$, (2) use the IH to substitute a lower bound for $\text{LHS}_k$, (3) finish with a side inequality that converts the IH-bound to $\text{RHS}_{k+1}$.
$\text{LHS}_{k+1} \;\overset{\text{IH}}{\geq}\; \text{something involving } k \;\geq\; \text{RHS}_{k+1}$
Key facts
- $2^n > n$ for all $n \geq 1$
- $n! > 2^n$ for all $n \geq 4$ (note the base shift)
- Bernoulli's inequality: $(1+x)^n \geq 1 + nx$ for $x > -1$ and $n \geq 1$
Concepts
- Why the inductive step must produce $\text{LHS}_{k+1} \geq \text{RHS}_{k+1}$ and not equality
- Why multiplying both sides of the IH by a positive preserves the direction
- Why a side inequality (e.g. $k \geq 1$) is often needed to close the chain
Skills
- Prove $2^n > n$, $n! > 2^n$, and Bernoulli's inequality by induction
- Choose the correct base case (often $n_0 > 1$)
- Build a chain of inequalities that points consistently the same direction
The same five-line structure as Lesson 07 — only the algebra inside the inductive step differs. The step becomes a chain of $\geq$ rather than a chain of $=$. Each link must point the same direction.
- State $P(n)$ as an inequality, e.g. "$P(n)$: $2^n > n$".
- Base at the smallest $n_0$ where the claim is true. For $n! > 2^n$ this is $n_0 = 4$ (note: $3! = 6 < 8 = 2^3$).
- Assume $P(k)$ as the IH.
- Show $\text{LHS}_{k+1} \geq \text{RHS}_{k+1}$ via a chain: rewrite $\text{LHS}_{k+1}$ in terms of $\text{LHS}_k$, apply the IH (multiplied by an appropriate positive), then close with a side inequality.
- Conclude.
Resolving the hook: $3! = 6$ and $2^3 = 8$ — so $n! > 2^n$ fails at $n = 3$. At $n = 4$: $4! = 24$ and $2^4 = 16$ — so the inequality first holds at $n = 4$. That is the correct base case.
Inequality induction uses the same 5-line template; chain of $\geq$ replaces chain of $=$ · Base case: smallest $n_0$ where the inequality first holds (often not $n = 1$) · $n! > 2^n$ starts at $n_0 = 4$; $2^n > n$ starts at $n_0 = 1$ · Always close with an explicit side inequality (e.g. $k \geq 1 \Rightarrow 2k \geq k+1$)
Pause — copy the inequality induction checklist: chain of $\geq$, correct base case $n_0$, and always closing with an explicit side inequality, into your book.
Quick check: What is the correct base case $n_0$ for proving $n! > 2^n$ by induction?
We just saw the inequality induction template where a chain of $\geq$ replaces $=$, requiring an explicit side inequality to close the step (e.g. $k \geq 1 \Rightarrow 2k \geq k+1$). That raises a question: what is the canonical example that exam questions model? This card answers it → Bernoulli's inequality $(1+x)^n \geq 1+nx$ for $x > -1$, where the condition $1+x > 0$ enables multiplying the IH.
Bernoulli's inequality is the canonical inequality-induction result: for $x > -1$ and integer $n \geq 1$,
The condition $x > -1$ matters: it makes $1 + x > 0$, which is what lets us multiply both sides of the IH by $(1+x)$ without flipping the inequality. The proof:
- Base: $n = 1$ gives $(1+x)^1 = 1+x \geq 1 + 1 \cdot x$ ✓ (equality, but $\geq$ holds).
- IH: $(1+x)^k \geq 1 + kx$ for some $k \geq 1$.
- Step: $(1+x)^{k+1} = (1+x)^k(1+x) \geq (1+kx)(1+x)$ since $1+x > 0$ and IH. Expand: $(1+kx)(1+x) = 1 + (k+1)x + kx^2 \geq 1 + (k+1)x$, since $kx^2 \geq 0$.
- Hence $P(k+1)$, conclude by induction.
Bernoulli: $(1+x)^n \geq 1 + nx$ for $x > -1$, $n \geq 1$ · Condition $x > -1 \Rightarrow 1+x > 0$ (lets us multiply IH by $1+x$) · Step: $(1+x)^{k+1} \geq (1+kx)(1+x) = 1 + (k+1)x + kx^2 \geq 1 + (k+1)x$ · Side inequality: $kx^2 \geq 0$ — write it explicitly
Pause — copy Bernoulli's inequality $(1+x)^n \geq 1+nx$ for $x>-1$, $n \geq 1$, the inductive step $(1+x)^{k+1} \geq (1+kx)(1+x) = 1+(k+1)x+kx^2 \geq 1+(k+1)x$, and the side inequality $kx^2 \geq 0$ into your book.
Did you get this? True or false: in the inductive step of Bernoulli's inequality, we use the fact that $1 + x > 0$ (which follows from $x > -1$) to multiply both sides of the IH $(1+x)^k \geq 1 + kx$ by $(1+x)$ without reversing the inequality.
Worked examples · 3 in a row, reveal as you go
Prove by induction that $2^n > n$ for all integers $n \geq 1$.
Prove by induction that $n! > 2^n$ for all integers $n \geq 4$.
Prove by induction that $(1+x)^n \geq 1 + nx$ for all integers $n \geq 1$ and all real $x > -1$.
Fill the gap: In the inductive step of $2^n > n$, we write $2^{k+1} = 2 \cdot 2^k > 2k$ (by IH). Then since $k \geq 1$, we have $2k \geq k + $. Hence $2^{k+1} > k+1$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: in proving $n! > 2^n$ by induction, it is acceptable to use $n_0 = 1$ as the base case provided we check that the inductive step works.
Activities · practice with the ideas
Prove by induction that $2^n > n$ for all $n \geq 1$. Show the IH multiplication and side inequality explicitly.
Prove by induction that $n! > 2^n$ for all $n \geq 4$. State why the base case must be $n_0 = 4$ and not $n_0 = 1$.
Prove Bernoulli's inequality: $(1+x)^n \geq 1 + nx$ for $x > -1$ and integer $n \geq 1$. Make every step (IH multiplication, side inequality $kx^2 \geq 0$) explicit.
Prove by induction that $3^n > 2n + 1$ for all $n \geq 2$. Identify the correct base case and the side inequality you need.
In the inductive step of Bernoulli's inequality, why is the condition $x > -1$ essential? What goes wrong if you allow $x = -2$?
Odd one out: Three of these statements about inequality induction are correct. Which one is NOT?
Earlier you sketched how to prove $2^n > n$: starting from $2^{k+1} = 2 \cdot 2^k$ and using the IH to bound this by $2k$.
The complete chain is: $2^{k+1} = 2 \cdot 2^k > 2k$ (by IH, multiplying by $2 > 0$), and since $k \geq 1$, $2k \geq k + 1$. Combining the two $\geq$ steps gives $2^{k+1} > k+1$. The side inequality $k \geq 1 \Rightarrow 2k \geq k+1$ is the part students most often skip — it's also the only thing standing between you and full marks.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove by induction that $2^n > n$ for all integers $n \geq 1$. (3 marks)
Q2. Prove by induction that $n! > 2^n$ for all integers $n \geq 4$. State why $n_0 = 4$ is the correct base case. (3 marks)
Q3. Prove Bernoulli's inequality $(1+x)^n \geq 1 + nx$ by induction for $x > -1$ and integer $n \geq 1$. Make explicit (a) where the IH is used, (b) where $1 + x > 0$ is used, and (c) where $kx^2 \geq 0$ is used. (4 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. $P(n)$: $2^n > n$. Base $n = 1$: $2 > 1$ ✓. Assume IH: $2^k > k$. Step: $2^{k+1} = 2 \cdot 2^k > 2k$ (IH × 2, valid as $2>0$). Side: $k \geq 1 \Rightarrow 2k \geq k+1$. So $2^{k+1} > k+1$. Conclude.
2. Inequality fails at $n = 1, 2, 3$ (e.g., $3! = 6 < 8 = 2^3$). Base $n = 4$: $24 > 16$ ✓. Assume $k! > 2^k$. Step: $(k+1)! = (k+1)k! > (k+1) \cdot 2^k \geq 2 \cdot 2^k = 2^{k+1}$ since $k + 1 \geq 5 > 2$. Hence $(k+1)! > 2^{k+1}$. Conclude.
3. $P(n)$: $(1+x)^n \geq 1 + nx$. Base $n = 1$: $(1+x) \geq 1 + x$ ✓ (equality). Assume IH $(1+x)^k \geq 1 + kx$. Step: $(1+x)^{k+1} = (1+x)^k(1+x) \geq (1+kx)(1+x)$ since $1 + x > 0$ (from $x > -1$). Expand: $1 + (k+1)x + kx^2 \geq 1 + (k+1)x$ since $kx^2 \geq 0$. Conclude.
4. Base $n = 2$: $9 > 5$ ✓. (Note $n=1$ gives $3 > 3$, false strictly.) Assume $3^k > 2k+1$. Step: $3^{k+1} = 3 \cdot 3^k > 3(2k+1) = 6k+3$. Side: $6k + 3 \geq 2(k+1)+1 = 2k+3$ iff $4k \geq 0$, true for $k \geq 2$. So $3^{k+1} > 2(k+1)+1$. Conclude (for $n \geq 2$).
5. The condition $x > -1$ gives $1 + x > 0$, so multiplying the IH by $1 + x$ preserves $\geq$. If $x = -2$, then $1+x = -1 < 0$, so multiplying would flip $\geq$ to $\leq$ and the chain breaks. Also $(1+x)^n = (-1)^n$ alternates between $1$ and $-1$, while $1+nx = 1 - 2n$ is large negative — Bernoulli still holds numerically but the inductive proof method fails.
Q1 (3 marks): State $P(n)$ + base ✓ [1]. Step: $2^{k+1} = 2 \cdot 2^k > 2k$ (IH used) [1]. Side inequality $2k \geq k+1$ + conclusion [1].
Q2 (3 marks): Justify base shift to $n_0 = 4$ with $3! = 6 < 8$ [1]. Base $4! = 24 > 16$ + assume IH [1]. Step uses IH and $k+1 \geq 5 > 2$; conclusion [1].
Q3 (4 marks): State $P(n)$ + base $n=1$ ✓ [1]. Assume IH; multiply by $(1+x)$ — note $1+x > 0$ from $x > -1$ [1]. Expand $(1+kx)(1+x) = 1 + (k+1)x + kx^2$; note $kx^2 \geq 0$ [1]. Conclude by induction with proper conclusion line [1].
Five timed questions on inequality induction, base shifts, and Bernoulli-type results. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering inequality-induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.