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$.
Start with the warm-up and record your first reasoning.
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.
Orient yourself to the lesson goals, language, and core approach.
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}$
Work through the concept and complete its check.
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.
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?
Build the next proof move and complete its check.
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:
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.
Follow the worked examples, then complete the check.
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 + m$, where $m =$ . Hence $2^{k+1} > k+1$.
Correct the common traps and test your understanding.
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.
Complete the practice activities and revisit your opening thinking.
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.
Multiple choice, then short answer under exam conditions.
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)
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].
Sit the module quiz, then close the lesson off.
A full module quiz covering every lesson in this module, not just this one. Set aside a decent block of time and treat it like a real assessment.
Start the module quiz →Tick when you've finished the practice and review.
Work through this topic 1-on-1 with an experienced HSC tutor.
Book a free session →