Induction for Inequalities I
Is $2^n$ always bigger than $n$? Intuitively yes — but can you prove it for every positive integer at once? Mathematical induction turns that intuition into an airtight argument. In this lesson you'll master the three-step inequality structure, learn the key “bridge the gap” technique, and prove results like $2^n > n$ and $n! > 2^{n-1}$ from scratch.
Without calculating, do you believe $2^n > n$ for every positive integer $n$? Try $n = 1, 2, 3, 4$ by hand. What pattern do you notice? Does the gap between $2^n$ and $n$ grow or shrink as $n$ increases?
Inequality proofs by induction follow the same three steps as all induction proofs, but the inductive step requires careful algebraic manipulation:
Step 1 — Base Case: Verify the inequality for the smallest relevant $n$. Sometimes that is $n = 1$; sometimes it is $n = 2$ or $n = 3$. Always check where the pattern actually starts.
Step 2 — Inductive Hypothesis: Assume the inequality holds for $n = k$. Write this clearly, e.g. "Assume $2^k > k$ for some positive integer $k$."
Step 3 — Inductive Step: Start with the LHS for $n = k + 1$. Apply an algebraic manipulation that introduces the hypothesis. Then show the result exceeds the RHS for $n = k + 1$.
Key facts
- The three steps of an inequality induction proof
- $2^n > n$ for all $n \geq 1$
- $n! > 2^{n-1}$ for all $n \geq 3$
- Factorial growth dominates exponential growth for large $n$
Concepts
- Why you must derive $P(k+1)$ from $P(k)$, not assume it
- The role of auxiliary inequalities in “bridging the gap”
- Why the base case must be chosen carefully for inequalities
Skills
- Write a complete, rigorous inequality induction proof
- Identify and prove the auxiliary inequality in the inductive step
- Determine the correct base case for a given inequality
The key to inequality induction is a two-part move in the inductive step:
- Substitute the hypothesis. Write the LHS for $n = k+1$, then replace a sub-expression using the inductive hypothesis $P(k)$ to introduce an inequality sign.
- Bridge the gap. After substitution you have an intermediate expression. Show that this intermediate expression still satisfies the required inequality by proving a short auxiliary result.
The intermediate expression is between the LHS and the target RHS. The auxiliary inequality must be proved from scratch — you cannot just say “this is obvious.”
The key to inequality induction is a two-part move in the inductive step:
Pause — copy the two-part inequality induction move: (1) apply hypothesis, (2) show the residual maintains the inequality for $k+1$ into your book.
Quick check: In the inductive step for an inequality proof, after applying the inductive hypothesis you obtain an expression that is not yet equal to the required RHS. What must you do next?
Worked examples · 2 full proofs, reveal step by step
Prove by mathematical induction that $2^n > n$ for all positive integers $n$.
Prove by mathematical induction that $n! > 2^{n-1}$ for all integers $n \geq 3$.
Did you get this? True or false: in the proof that $2^n > n$, the auxiliary inequality needed is $2k \geq k + 1$, which holds for all $k \geq 1$.
We just saw that the two-part inequality induction move applies the hypothesis to one side, then shows the residual term preserves the inequality for $n=k+1$. That raises a question: what formulas, templates, and conclusion wording should you have memorised before tackling these proofs independently? This card answers it → the core inequality templates and HSC conclusion phrasing.
- Start from the stronger side: Begin with the LHS for $n = k+1$ and use the hypothesis to introduce an inequality.
- Bridge the gap: After substitution, prove an auxiliary inequality to close the argument. Show $k - 1 \geq 0$ explicitly; do not say “obvious.”
- Base case choice: Some inequalities only hold for $n \geq n_0$; always check where the pattern begins and state it.
- Factorial growth: $n!$ grows faster than any exponential $a^n$ for large $n$, making factorial inequalities powerful and common in HSC.
Key concept: Key concepts summary.
Pause — copy the key inequality induction templates and the required conclusion wording into your book.
Fill the gap: To complete the inductive step in the proof of $2^n > n$, after writing $2^{k+1} = 2 \cdot 2^k > 2k$, you must show that $2k \geq k + $ .
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: for the statement $n! > 2^{n-1}$, the correct base case is $n = 1$.
Activities · practice with the ideas
Verify the base case ($n = 1$) for $2^n > n$, showing your working clearly.
Write out the inductive hypothesis and the statement to be proved (i.e. $P(k+1)$) for the inequality $2^n > n$.
Prove the auxiliary inequality $2k \geq k+1$ for all positive integers $k$.
Identify the correct base case for the statement $3^n > n^2$. Is it $n=1$, $n=2$, or $n=3$? Verify by substitution.
Prove by induction that $3^n > n^2$ for all $n \geq 1$. (Hint: you will need to show $3k^2 \geq (k+1)^2$ as the auxiliary.)
Odd one out: Three of these statements about inequality induction are correct. Which one is NOT?
Earlier you considered whether $2^n > n$ for large $n$ like $n = 1{,}000{,}000$.
The induction proof you just studied guarantees this for every positive integer — not just the ones you can check by hand. The key insight: each step only needs to prove $P(k) \Rightarrow P(k+1)$. Because we verified the base case and the chain of implication is unbroken, the truth extends forever. Even for $n = 10^{100}$.
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 the auxiliary inequality $2k \geq k + 1$ for all positive integers $k$. (2 marks)
Q2. Prove by mathematical induction that $2^n > n$ for all positive integers $n$. (3 marks)
Q3. Prove by mathematical induction that $n! > 2^{n-1}$ for all integers $n \geq 3$. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. LHS $= 2^1 = 2$, RHS $= 1$; $2 > 1$ ✓
2. Hypothesis: assume $2^k > k$. To prove: $2^{k+1} > k+1$.
3. $2k - (k+1) = k - 1 \geq 0$ for $k \geq 1$. Therefore $2k \geq k+1$.
4. Test $n=1$: $3 > 1$ ✓. Base case is $n = 1$.
5. Base case $n=1$: $3^1=3>1=1^2$ ✓. Hypothesis: $3^k>k^2$. Step: $3^{k+1}=3\cdot3^k>3k^2$. Auxiliary: $3k^2\geq(k+1)^2 \Leftrightarrow 3k^2-k^2-2k-1=2k^2-2k-1\geq0$ for $k\geq2$ ✓.
Q1 (2 marks): $2k - (k+1) = k-1 \geq 0$ for all $k \geq 1$ [1]. Therefore $2k \geq k+1$ for all positive integers $k$ [1].
Q2 (3 marks): Base: $n=1$: $2^1=2>1$ ✓ [1]. Hyp: assume $2^k>k$. Step: $2^{k+1}=2\cdot2^k>2k\geq k+1$ (since $k\geq1$), so $2^{k+1}>k+1$ [2]. Conclude by induction [1 across steps].
Q3 (3 marks): Base: $n=3$: $6>4$ ✓ [1]. Hyp: assume $k!>2^{k-1}$. Step: $(k+1)!=(k+1)\cdot k!>(k+1)\cdot2^{k-1}>2\cdot2^{k-1}=2^k$ (since $k+1\geq4>2$) [2]. By induction, true for all $n\geq3$ [1 across steps].
Five timed questions. 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.