Induction on Inequalities

[MathDefinition title="Inequalities with Induction"] Mathematical induction can be used to prove inequalities that hold for all natural numbers greater than or equal to some starting value. The process is similar to proving equalities but requires careful handling of inequalities. [/MathDefinition]

[MathKeyFormula title="Key Inequality Facts"]

1. If a > b and c > 0, then ac > bc
2. If a > b, then a + c > b + c
3. For n ≥ 1: 2ⁿ > n
4. For n ≥ 5: n! > 2ⁿ
5. For n ≥ 2: (1 + 1/n)ⁿ < 3
6. Bernoulli's inequality: (1 + x)ⁿ ≥ 1 + nx for x > −1, n ≥ 1 [/MathKeyFormula]

[MathNote title="Tips for Inequality Proofs"]

1. In the inductive step, you may need to show P(k+1) > something > target
2. Often you'll need to add or multiply both sides by positive quantities
3. Be careful when multiplying by negative numbers (inequality sign flips)
4. Sometimes you need to use a stronger inductive hypothesis [/MathNote]

[MathExample title="Example 1: 2ⁿ > n²"] Problem: Prove that 2ⁿ > n² for all n ≥ 5.

Solution: Let P(n): 2ⁿ > n²

Step 1: Base case (n = 5) 2⁵ = 32, 5² = 25 32 > 25, so P(5) is true.

Step 2: Inductive hypothesis Assume P(k) is true for some k ≥ 5: 2ᵏ > k²

Step 3: Prove P(k+1) We need to show: 2ᵏ⁺¹ > (k+1)²

2ᵏ⁺¹ = 2·2ᵏ > 2k² [using inductive hypothesis]

We need to show 2k² > (k+1)²: 2k² > k² + 2k + 1 k² − 2k − 1 > 0 (k − 1)² > 2

Since k ≥ 5, (k − 1)² ≥ 16 > 2, so this is true.

Therefore, 2ᵏ⁺¹ > 2k² > (k+1)²

Step 4: Conclusion By mathematical induction, 2ⁿ > n² for all n ≥ 5. [/MathExample]

[MathExample title="Example 2: n! > 3ⁿ"] Problem: Prove that n! > 3ⁿ for all n ≥ 7.

Solution: Let P(n): n! > 3ⁿ

Step 1: Base case (n = 7) 7! = 5040, 3⁷ = 2187 5040 > 2187, so P(7) is true.

Step 2: Inductive hypothesis Assume P(k) is true for some k ≥ 7: k! > 3ᵏ

Step 3: Prove P(k+1) We need to show: (k+1)! > 3ᵏ⁺¹

(k+1)! = (k+1)·k! > (k+1)·3ᵏ [using inductive hypothesis]

Since k ≥ 7, we have k + 1 ≥ 8 > 3

Therefore, (k+1)·3ᵏ > 3·3ᵏ = 3ᵏ⁺¹

So, (k+1)! > 3ᵏ⁺¹

Step 4: Conclusion By mathematical induction, n! > 3ⁿ for all n ≥ 7. [/MathExample]

[MathExample title="Example 3: Sum of Reciprocals"] Problem: Prove that 1/1² + 1/2² + 1/3² + ... + 1/n² < 2 − 1/n for all n ≥ 2.

Solution: Let P(n): 1/1² + 1/2² + ... + 1/n² < 2 − 1/n

Step 1: Base case (n = 2) LHS = 1 + 1/4 = 5/4 = 1.25 RHS = 2 − 1/2 = 3/2 = 1.5 1.25 < 1.5, so P(2) is true.

Step 2: Inductive hypothesis Assume P(k) is true for some k ≥ 2: 1/1² + 1/2² + ... + 1/k² < 2 − 1/k

Step 3: Prove P(k+1) We need to show: 1/1² + 1/2² + ... + 1/k² + 1/(k+1)² < 2 − 1/(k+1)

LHS < 2 − 1/k + 1/(k+1)² [using inductive hypothesis]

We need to show: 2 − 1/k + 1/(k+1)² < 2 − 1/(k+1)

−1/k + 1/(k+1)² < −1/(k+1)

1/(k+1)² < 1/k − 1/(k+1) = 1/(k(k+1))

Since k < k+1, we have k(k+1) < (k+1)², so 1/(k(k+1)) > 1/(k+1)²

This confirms the inequality.

Step 4: Conclusion By mathematical induction, the inequality holds for all n ≥ 2. [/MathExample]

[MathExample title="Example 4: Bernoulli's Inequality"] Problem: Prove that (1 + x)ⁿ ≥ 1 + nx for x > −1, n ∈ N.

Solution: Let P(n): (1 + x)ⁿ ≥ 1 + nx

Step 1: Base case (n = 1) (1 + x)¹ = 1 + x 1 + 1·x = 1 + x LHS = RHS, so P(1) is true.

Step 2: Inductive hypothesis Assume P(k) is true: (1 + x)ᵏ ≥ 1 + kx

Step 3: Prove P(k+1) We need to show: (1 + x)ᵏ⁺¹ ≥ 1 + (k+1)x

(1 + x)ᵏ⁺¹ = (1 + x)·(1 + x)ᵏ ≥ (1 + x)(1 + kx) [using inductive hypothesis, since 1 + x > 0]

= 1 + kx + x + kx² = 1 + (k+1)x + kx²

Since kx² ≥ 0 (as k ≥ 1 and x² ≥ 0): 1 + (k+1)x + kx² ≥ 1 + (k+1)x

Therefore, (1 + x)ᵏ⁺¹ ≥ 1 + (k+1)x

Step 4: Conclusion By mathematical induction, (1 + x)ⁿ ≥ 1 + nx for all n ∈ N and x > −1. [/MathExample]