This is a beta course, so its structure, chapters, and examples may continue to change.
Proving Inequalities
Proving inequalities with mathematical induction requires more technique, especially since the inductive step often needs clever magnification or reduction.
Proof Strategy
The key to proving the inequality f ( n ) ≥ g ( n ) f(n) \geq g(n) f ( n ) ≥ g ( n ) (or f ( n ) ≤ g ( n ) f(n) \leq g(n) f ( n ) ≤ g ( n ) ):
Core technique : in the inductive step, establish the relationship between
f ( k + 1 ) f(k+1) f ( k + 1 ) and
f ( k ) f(k) f ( k ) through magnification or reduction, then use the inductive hypothesis.
Common methods of magnification and reduction:
Adding or subtracting positive terms
Using known inequalities (e.g., 2 n > n 2^n > n 2 n > n )
Fraction magnification or reduction
Worked Examples
Example 1: Exponential Greater Than Polynomial
Proposition : prove that 2 n > n 2 2^n > n^2 2 n > n 2 for all n ≥ 5 n \geq 5 n ≥ 5 .
Proof :
Base case : when n = 5 n = 5 n = 5 , 2 5 = 32 > 25 = 5 2 2^5 = 32 > 25 = 5^2 2 5 = 32 > 25 = 5 2 , holds.
Inductive hypothesis : assume 2 k > k 2 2^k > k^2 2 k > k 2 (k ≥ 5 k \geq 5 k ≥ 5 )
Inductive step : we need to prove 2 k + 1 > ( k + 1 ) 2 2^{k+1} > (k+1)^2 2 k + 1 > ( k + 1 ) 2
2 k + 1 = 2 ⋅ 2 k > 2 k 2 (inductive hypothesis) \begin{aligned}
2^{k+1} &= 2 \cdot 2^k \\
&> 2k^2 \quad \text{(inductive hypothesis)}
\end{aligned} 2 k + 1 = 2 ⋅ 2 k > 2 k 2 (inductive hypothesis)
Now we need to prove 2 k 2 > ( k + 1 ) 2 = k 2 + 2 k + 1 2k^2 > (k+1)^2 = k^2 + 2k + 1 2 k 2 > ( k + 1 ) 2 = k 2 + 2 k + 1
That is, prove k 2 > 2 k + 1 k^2 > 2k + 1 k 2 > 2 k + 1 , i.e., k 2 − 2 k − 1 > 0 k^2 - 2k - 1 > 0 k 2 − 2 k − 1 > 0
When k ≥ 5 k \geq 5 k ≥ 5 , k 2 − 2 k − 1 = ( k − 1 ) 2 − 2 ≥ 16 − 2 = 14 > 0 k^2 - 2k - 1 = (k-1)^2 - 2 \geq 16 - 2 = 14 > 0 k 2 − 2 k − 1 = ( k − 1 ) 2 − 2 ≥ 16 − 2 = 14 > 0
Therefore 2 k + 1 > 2 k 2 > ( k + 1 ) 2 2^{k+1} > 2k^2 > (k+1)^2 2 k + 1 > 2 k 2 > ( k + 1 ) 2
Conclusion : by mathematical induction, the inequality holds for all n ≥ 5 n \geq 5 n ≥ 5 .
Example 2: Bernoulli’s Inequality
Proposition : prove that ( 1 + x ) n ≥ 1 + n x (1+x)^n \geq 1 + nx ( 1 + x ) n ≥ 1 + n x , where x > − 1 x > -1 x > − 1 and n ∈ N ∗ n \in \mathbb{N}^* n ∈ N ∗
Proof :
Base case : when n = 1 n = 1 n = 1 , ( 1 + x ) 1 = 1 + x ≥ 1 + x (1+x)^1 = 1 + x \geq 1 + x ( 1 + x ) 1 = 1 + x ≥ 1 + x , holds.
Inductive hypothesis : assume ( 1 + x ) k ≥ 1 + k x (1+x)^k \geq 1 + kx ( 1 + x ) k ≥ 1 + k x
Inductive step :
( 1 + x ) k + 1 = ( 1 + x ) k ⋅ ( 1 + x ) ≥ ( 1 + k x ) ( 1 + x ) (inductive hypothesis, since 1 + x > 0 ) = 1 + k x + x + k x 2 = 1 + ( k + 1 ) x + k x 2 ≥ 1 + ( k + 1 ) x (since k x 2 ≥ 0 ) \begin{aligned}
(1+x)^{k+1} &= (1+x)^k \cdot (1+x) \\
&\geq (1 + kx)(1 + x) \quad \text{(inductive hypothesis, since $1+x > 0$)} \\
&= 1 + kx + x + kx^2 \\
&= 1 + (k+1)x + kx^2 \\
&\geq 1 + (k+1)x \quad \text{(since $kx^2 \geq 0$)}
\end{aligned} ( 1 + x ) k + 1 = ( 1 + x ) k ⋅ ( 1 + x ) ≥ ( 1 + k x ) ( 1 + x ) (inductive hypothesis, since 1 + x > 0) = 1 + k x + x + k x 2 = 1 + ( k + 1 ) x + k x 2 ≥ 1 + ( k + 1 ) x (since k x 2 ≥ 0)
Conclusion : by mathematical induction, the inequality holds.
Example 3: The Harmonic Series Diverges
Proposition : prove that 1 + 1 2 + 1 3 + ⋯ + 1 2 n > n 2 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n} > \frac{n}{2} 1 + 2 1 + 3 1 + ⋯ + 2 n 1 > 2 n for all n ≥ 1 n \geq 1 n ≥ 1 .
Proof :
Base case : when n = 1 n = 1 n = 1 , 1 + 1 2 = 3 2 > 1 2 1 + \frac{1}{2} = \frac{3}{2} > \frac{1}{2} 1 + 2 1 = 2 3 > 2 1 , holds.
Inductive hypothesis : assume 1 + 1 2 + ⋯ + 1 2 k > k 2 1 + \frac{1}{2} + \cdots + \frac{1}{2^k} > \frac{k}{2} 1 + 2 1 + ⋯ + 2 k 1 > 2 k
Inductive step :
1 + 1 2 + ⋯ + 1 2 k + 1 2 k + 1 + ⋯ + 1 2 k + 1 > k 2 + 1 2 k + 1 + ⋯ + 1 2 k + 1 (inductive hypothesis) \begin{aligned}
&1 + \frac{1}{2} + \cdots + \frac{1}{2^k} + \frac{1}{2^k+1} + \cdots + \frac{1}{2^{k+1}} \\
&> \frac{k}{2} + \frac{1}{2^k+1} + \cdots + \frac{1}{2^{k+1}} \quad \text{(inductive hypothesis)}
\end{aligned} 1 + 2 1 + ⋯ + 2 k 1 + 2 k + 1 1 + ⋯ + 2 k + 1 1 > 2 k + 2 k + 1 1 + ⋯ + 2 k + 1 1 (inductive hypothesis)
There are 2 k 2^k 2 k terms from 2 k + 1 2^k+1 2 k + 1 to 2 k + 1 2^{k+1} 2 k + 1 , and each term is ≥ 1 2 k + 1 \geq \frac{1}{2^{k+1}} ≥ 2 k + 1 1 :
> k 2 + 2 k ⋅ 1 2 k + 1 = k 2 + 1 2 = k + 1 2 \begin{aligned}
&> \frac{k}{2} + 2^k \cdot \frac{1}{2^{k+1}} \\
&= \frac{k}{2} + \frac{1}{2} \\
&= \frac{k+1}{2}
\end{aligned} > 2 k + 2 k ⋅ 2 k + 1 1 = 2 k + 2 1 = 2 k + 1
Conclusion : by mathematical induction, the inequality holds.
Practice Problems
Exercise 1
Prove: n ! > 2 n n! > 2^n n ! > 2 n for all n ≥ 4 n \geq 4 n ≥ 4 .
Reference Answer mathematical induction inequality proof
Approach : Use mathematical induction: verify the inequality at the starting value n = 4 n = 4 n = 4 , then carry the induction hypothesis over to the n + 1 n + 1 n + 1 case.
Steps :
Base case : when n = 4 n = 4 n = 4 , 4 ! = 24 > 16 = 2 4 4! = 24 > 16 = 2^4 4 ! = 24 > 16 = 2 4 , holds.
Inductive hypothesis : assume k ! > 2 k k! > 2^k k ! > 2 k (k ≥ 4 k \geq 4 k ≥ 4 )
Inductive step :
( k + 1 ) ! = ( k + 1 ) ⋅ k ! > ( k + 1 ) ⋅ 2 k (inductive hypothesis) > 2 ⋅ 2 k (because k + 1 > 2 when k ≥ 4 ) = 2 k + 1 \begin{aligned}
(k+1)! &= (k+1) \cdot k! \\
&> (k+1) \cdot 2^k \quad \text{(inductive hypothesis)} \\
&> 2 \cdot 2^k \quad \text{(because $k+1 > 2$ when $k \geq 4$)} \\
&= 2^{k+1}
\end{aligned} ( k + 1 )! = ( k + 1 ) ⋅ k ! > ( k + 1 ) ⋅ 2 k (inductive hypothesis) > 2 ⋅ 2 k (because k + 1 > 2 when k ≥ 4) = 2 k + 1 Conclusion : by mathematical induction, the inequality holds.
Answer : By mathematical induction, the inequality holds.
Exercise 2
Prove: 1 n + 1 + 1 n + 2 + ⋯ + 1 2 n > 13 24 \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} > \frac{13}{24} n + 1 1 + n + 2 1 + ⋯ + 2 n 1 > 24 13 for all n ≥ 2 n \geq 2 n ≥ 2 .
Reference Answer mathematical induction inequality proof
Approach : Use mathematical induction: verify the inequality at n = 2 n = 2 n = 2 , then carry the induction hypothesis over to the n + 1 n + 1 n + 1 case.
Steps :
Base case : when n = 2 n = 2 n = 2 , 1 3 + 1 4 = 7 12 > 13 24 \frac{1}{3} + \frac{1}{4} = \frac{7}{12} > \frac{13}{24} 3 1 + 4 1 = 12 7 > 24 13 , holds.
Inductive hypothesis : assume 1 k + 1 + ⋯ + 1 2 k > 13 24 \frac{1}{k+1} + \cdots + \frac{1}{2k} > \frac{13}{24} k + 1 1 + ⋯ + 2 k 1 > 24 13
Inductive step :
1 k + 2 + ⋯ + 1 2 k + 1 2 k + 1 + 1 2 k + 2 = ( 1 k + 1 + ⋯ + 1 2 k ) − 1 k + 1 + 1 2 k + 1 + 1 2 k + 2 > 13 24 − 1 k + 1 + 1 2 k + 1 + 1 2 k + 2 \begin{aligned}
&\frac{1}{k+2} + \cdots + \frac{1}{2k} + \frac{1}{2k+1} + \frac{1}{2k+2} \\
&= \left(\frac{1}{k+1} + \cdots + \frac{1}{2k}\right) - \frac{1}{k+1} + \frac{1}{2k+1} + \frac{1}{2k+2} \\
&> \frac{13}{24} - \frac{1}{k+1} + \frac{1}{2k+1} + \frac{1}{2k+2}
\end{aligned} k + 2 1 + ⋯ + 2 k 1 + 2 k + 1 1 + 2 k + 2 1 = ( k + 1 1 + ⋯ + 2 k 1 ) − k + 1 1 + 2 k + 1 1 + 2 k + 2 1 > 24 13 − k + 1 1 + 2 k + 1 1 + 2 k + 2 1 We need to prove − 1 k + 1 + 1 2 k + 1 + 1 2 k + 2 > 0 -\frac{1}{k+1} + \frac{1}{2k+1} + \frac{1}{2k+2} > 0 − k + 1 1 + 2 k + 1 1 + 2 k + 2 1 > 0
i.e., 1 2 k + 1 + 1 2 k + 2 > 1 k + 1 \frac{1}{2k+1} + \frac{1}{2k+2} > \frac{1}{k+1} 2 k + 1 1 + 2 k + 2 1 > k + 1 1
This holds for k ≥ 2 k \geq 2 k ≥ 2 .
Conclusion : by mathematical induction, the inequality holds.
Answer : By mathematical induction, the inequality holds.
Summary
Symbols Used in This Article
Symbol notation
Symbol Type Pronunciation/Explanation Meaning in This Article f ( n ) , g ( n ) f(n), g(n) f ( n ) , g ( n ) Mathematical symbol f/g of n The expressions on the two sides of the inequality n , k n, k n , k Mathematical symbol n, k Natural numbers ≥ \geq ≥ Mathematical symbol greater than or equal to Greater than or equal to ≤ \leq ≤ Mathematical symbol less than or equal to Less than or equal to x x x Mathematical symbol x The variable in Bernoulli’s inequality N ∗ \mathbb{N}^* N ∗ Mathematical symbol positive integers The set of positive integers n ! n! n ! Mathematical symbol n factorial The factorial of n n n 1 n \frac{1}{n} n 1 Mathematical symbol one over n The reciprocal