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 ) 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 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
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 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 x > − 1 x > -1 x > − 1 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
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 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
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 2 k + 1 2^k+1 2 k + 1 2 k + 1 2^{k+1} 2 k + 1 ≥ 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 n ≥ 4 n \geq 4 n ≥ 4
Reference Answer (2 个标签)
mathematical induction inequality proof
Base case : when n = 4 n = 4 n = 4 4 ! = 24 > 16 = 2 4 4! = 24 > 16 = 2^4 4 ! = 24 > 16 = 2 4
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.
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 n ≥ 2 n \geq 2 n ≥ 2
Reference Answer (2 个标签)
mathematical induction inequality proof
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
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.
Summary Symbols Used in This Article
符号 类型 读音/说明 在本文中的含义 f ( n ) , g ( n ) f(n), g(n) f ( n ) , g ( n ) 数学符号 f/g of n The expressions on the two sides of the inequality n , k n, k n , k 数学符号 n, k Natural numbers ≥ \geq ≥ 数学符号 greater than or equal to Greater than or equal to ≤ \leq ≤ 数学符号 less than or equal to Less than or equal to x x x 数学符号 x The variable in Bernoulli’s inequality N ∗ \mathbb{N}^* N ∗ 数学符号 positive integers The set of positive integers n ! n! n ! 数学符号 n factorial The factorial of n n n 1 n \frac{1}{n} n 1 数学符号 one over n The reciprocal
中英对照
中文术语 英文术语 音标 说明 放缩法 magnification-reduction /ˌmæɡnɪfɪˈkeɪʃən rɪˈdʌkʃən/ Establishing inequalities by magnifying or reducing 伯努利不等式 Bernoulli’s inequality /bɜːˈnuːli ɪnɪˈkwɒləti/ ( 1 + x ) n ≥ 1 + n x (1+x)^n \geq 1+nx ( 1 + x ) n ≥ 1 + n x 调和级数 harmonic series /hɑːˈmɒnɪk ˈsɪəriːz/ ∑ 1 n \sum \frac{1}{n} ∑ n 1 数学归纳法 mathematical induction /ˌmæθəˈmætɪkəl ɪnˈdʌkʃən/ A proof method from the base case to the general 阶乘 factorial /fækˈtɔːriəl/ n ! = 1 × 2 × ⋯ × n n! = 1 \times 2 \times \cdots \times n n ! = 1 × 2 × ⋯ × n
