1
The base case is where the claim starts holding
2ⁿ > n² is false at n = 2, 3, 4. Its base case is n = 5, and claiming it from n = 1 makes the statement false.
Lesson · Induction and Recursion · Induction
Induction with Inequalities and Divisibility
Inequalities like 2ⁿ > n² fail for small n and hold from some point on, so the base case moves. Divisibility claims need the hypothesis to supply a multiple, which changes what the algebra is aiming at.
2ⁿ > n² FALSE for n = 2, 3, 4; TRUE from n = 5
n! > 2ⁿ TRUE from n = 4
divisibility: write the k+1 case as (k case) + (obvious multiple)
Bernoulli: (1 + x)ⁿ ≥ 1 + nx for x ≥ −1
Where the base case moves
Core ideas
What this lesson establishes
Both families need the same three parts, and both introduce a wrinkle: finding where the claim actually starts, and knowing what the step must produce.
2
Divisibility steps aim for an explicit multiple
To show d | f(k+1), rewrite f(k+1) as f(k) plus something visibly divisible by d, then apply the hypothesis.
3
Inequality steps often need a second fact
Going from 2^{k+1} > 2k² to (k+1)² needs 2k² ≥ (k+1)², which is true only for k ≥ 3. That side condition is part of the proof.
The material
Inequalities and divisibility
One worked proof of each, with the side conditions made explicit.
Inequalities
Theorem · 2ⁿ > n² for n ≥ 5
The inequality fails at n = 2, 3, 4 and holds for every n ≥ 5.
Base. At n = 5: 2⁵ = 32 > 25 = 5².
Step. Let k ≥ 5 and assume 2^k > k². Then 2^{k+1} = 2 · 2^k > 2k² by the hypothesis.
It remains to show 2k² ≥ (k+1)² for k ≥ 5. Expanding, this is 2k² ≥ k² + 2k + 1, that is k² − 2k − 1 ≥ 0, that is (k−1)² ≥ 2, which holds for every k ≥ 3 and in particular for k ≥ 5.
Chaining: 2^{k+1} > 2k² ≥ (k+1)².
□
The second half of that step is a separate inequality that has nothing to do with induction, and it is where the proof actually lives. Induction supplied 2^k > k²; ordinary algebra supplied the bridge from 2k² to (k+1)².
Finding the right base case is part of the problem. Evaluate the claim at n = 1, 2, 3, … until it starts holding, and check that it does not fail again later — which the inductive step is what guarantees.
Theorem · Bernoulli's inequality
For x ≥ −1 and n ≥ 0, (1 + x)ⁿ ≥ 1 + nx.
Base. At n = 0 both sides are 1.
Step. Assume (1+x)^k ≥ 1 + kx. Since x ≥ −1, the factor 1 + x is non-negative, so multiplying the inequality by it preserves the direction:
(1+x)^{k+1} ≥ (1 + kx)(1 + x) = 1 + (k+1)x + kx² ≥ 1 + (k+1)x,
the last step because kx² ≥ 0.
□
The hypothesis x ≥ −1 was used exactly once, to justify multiplying an inequality by 1 + x without flipping it. That is the kind of step that is easy to perform silently and wrong to perform without the condition.
Divisibility
Theorem · 3 | (n³ + 2n) for every n ≥ 0
The integer n³ + 2n is divisible by 3 for every natural n.
Base. At n = 0: 0 is divisible by 3.
Step. Assume 3 | (k³ + 2k), so k³ + 2k = 3m for some integer m. Then
(k+1)³ + 2(k+1) = k³ + 3k² + 3k + 1 + 2k + 2 = (k³ + 2k) + 3(k² + k + 1) = 3m + 3(k² + k + 1) = 3(m + k² + k + 1),
which is divisible by 3.
□
The whole technique is in the regrouping: separate the expression into the k case plus a remainder, and show the remainder is visibly a multiple. If the remainder is not visibly a multiple, the regrouping was wrong, not the claim.
Interactive
Check P(n), then notice checking is not proving
Two of these statements are false
Method
Inequalities and divisibility
Locate the base case first; it is not always 1.
1
Evaluate the claim at small n
Find the first n where it holds. That is your base case, and starting earlier makes the theorem false.
2
For an inequality, chain through the hypothesis
Apply the hypothesis to get a bound, then bridge from that bound to the target with ordinary algebra — and state the range where the bridge holds.
3
For divisibility, regroup as (k case) + (multiple)
Expand f(k+1), extract f(k), and show what remains is a visible multiple of d.
4
Check every inequality manipulation
Multiplying by a possibly-negative quantity flips the direction. Bernoulli's hypothesis x ≥ −1 exists for exactly this reason.
Inequalities and divisibility
Score 0 / 0Choose the answer you can justify.
Prove n! > 2ⁿ for n ≥ 4
It fails at n = 1, 2, 3: 1 < 2, 2 < 4, 6 < 8.
BASE n = 4: 4! = 24 > 16 = 2⁴. ✓
STEP Let k ≥ 4 and assume k! > 2ᵏ.
(k+1)! = (k+1)·k!
> (k+1)·2ᵏ ← hypothesis, and k+1 > 0
≥ 5·2ᵏ ← since k ≥ 4
> 2·2ᵏ = 2ᵏ⁺¹
CONCLUDE n! > 2ⁿ for every n ≥ 4. ∎
The k + 1 > 0 note matters: multiplying an inequality by a factor is only safe when the factor is positive. It is true here for trivial reasons, and writing it is the difference between a proof and a manipulation that happens to work.
Common mistakes
1
Starting the induction at n = 1 out of habitSeveral standard inequalities fail for small n. The base case belongs where the claim starts holding, and stating it elsewhere makes the theorem false as written.
2
Multiplying an inequality by a possibly-negative quantityThe direction flips. Every such step needs the sign of the factor stated.
3
Leaving the divisibility remainder unfactored"3k² + 3k + 3 is divisible by 3" is only convincing once written as 3(k² + k + 1). Show the factor.
Check your understanding
✓
Finish when you can locate a base case by testing rather than by assuming.
Find the smallest n from which 2ⁿ > n³ holds and stays true. Test n = 1, 2, 3, … and keep going past the first failure: the claim is true at n = 1, false from 2 to 9, and true from n = 10 on (1024 > 1000). Prove it from there, and state the side inequality your step needed — the bridge is 2k³ ≥ (k+1)³, which fails at k = 3 and holds from k = 4, so it is available at every k the step uses. Both halves are the lesson, and so is noticing that the base case sits well past the point where the bridge starts working.
Note: An inequality proof usually splits into an induction and a piece of ordinary algebra. Isolating the second piece as its own claim — "it suffices to show 2k² ≥ (k+1)² for k ≥ 3" — makes the proof much easier to check.