Solutions — Proof by Induction: Inequalities

Step 1 — Base case (n = 1):

2¹ = 2 ≥ 2 = 1+1. ✓

Step 2 — Inductive hypothesis:

Assume 2^k ≥ k+1 for some integer k ≥ 1.

Step 3 — Inductive step: Show 2^k+1 ≥ (k+1)+1 = k+2.

2^k+1 = 2 × 2^k ≥ 2(k+1) = 2k+2     [by hypothesis]

Since k ≥ 1, we have 2k+2 ≥ k+2 (because k ≥ 0 always). ✓

Therefore 2^k+1 ≥ 2k+2 ≥ k+2 = (k+1)+1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2ⁿ ≥ n+1 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

1! = 1 = 2⁰ = 1. ✓ (equality holds)

Step 2 — Inductive hypothesis:

Assume k! ≥ 2^k−1 for some integer k ≥ 1.

Step 3 — Inductive step: Show (k+1)! ≥ 2^(k+1)−1 = 2^k.

(k+1)! = (k+1) × k! ≥ (k+1) × 2^k−1     [by hypothesis]

Since k ≥ 1, we have k+1 ≥ 2, so (k+1) × 2^k−1 ≥ 2 × 2^k−1 = 2^k. ✓

Therefore (k+1)! ≥ 2^k = 2^(k+1)−1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, n! ≥ 2ⁿ⁻¹ for all integers n ≥ 1.

Step 1 — Base case (n = 1):

1² = 1 ≥ 1 = 2(1)−1. ✓

Step 2 — Inductive hypothesis:

Assume k² ≥ 2k−1 for some integer k ≥ 1.

Step 3 — Inductive step: Show (k+1)² ≥ 2(k+1)−1 = 2k+1.

(k+1)² = k² + 2k + 1 ≥ (2k−1) + 2k + 1 = 4k     [by hypothesis]

Need to show 4k ≥ 2k+1, i.e. 2k ≥ 1. This holds for all k ≥ 1. ✓

Therefore (k+1)² ≥ 4k ≥ 2k+1 = 2(k+1)−1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, n² ≥ 2n−1 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

3¹ = 3 ≥ 3 = 2(1)+1. ✓

Step 2 — Inductive hypothesis:

Assume 3^k ≥ 2k+1 for some integer k ≥ 1.

Step 3 — Inductive step: Show 3^k+1 ≥ 2(k+1)+1 = 2k+3.

3^k+1 = 3 × 3^k ≥ 3(2k+1) = 6k+3     [by hypothesis]

Need to show 6k+3 ≥ 2k+3, i.e. 4k ≥ 0. True for all k ≥ 1. ✓

Therefore 3^k+1 ≥ 6k+3 ≥ 2k+3 = 2(k+1)+1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 3ⁿ ≥ 2n+1 for all integers n ≥ 1.

Step 1 — Base case (n = 4):

4! = 24 > 16 = 2⁴. ✓

Note: n=3 fails (3!=6 < 8=2³), so n=4 is the correct starting point.

Step 2 — Inductive hypothesis:

Assume k! > 2^k for some integer k ≥ 4.

Step 3 — Inductive step: Show (k+1)! > 2^k+1.

(k+1)! = (k+1) × k! > (k+1) × 2^k     [by hypothesis]

Since k ≥ 4, we have k+1 ≥ 5 > 2, so (k+1) × 2^k > 2 × 2^k = 2^k+1. ✓

Therefore (k+1)! > 2^k+1. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, n! > 2ⁿ for all integers n ≥ 4.

Step 1 — Base case (n = 4):

2⁴ = 16 = 4². ✓ (equality holds)

Step 2 — Inductive hypothesis:

Assume 2^k ≥ k² for some integer k ≥ 4.

Step 3 — Inductive step: Show 2^k+1 ≥ (k+1)².

2^k+1 = 2 × 2^k ≥ 2k²     [by hypothesis]

Need to show 2k² ≥ (k+1)² = k²+2k+1, i.e. k²−2k−1 ≥ 0.

For k ≥ 4: k²−2k−1 ≥ 16−8−1 = 7 > 0. ✓

Therefore 2^k+1 ≥ 2k² ≥ (k+1)². ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2ⁿ ≥ n² for all integers n ≥ 4.

Step 1 — Base case (n = 1):

(1+x)¹ = 1+x = 1+(1)x. ✓

Step 2 — Inductive hypothesis:

Assume (1+x)^k ≥ 1+kx for some integer k ≥ 1.

Step 3 — Inductive step: Show (1+x)^k+1 ≥ 1+(k+1)x.

(1+x)^k+1 = (1+x) × (1+x)^k

≥ (1+x)(1+kx)     [by hypothesis; multiplication by (1+x) > 0 preserves ≥]

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

Since k ≥ 1 and x ≥ 0:   kx² ≥ 0, so:

1 + (k+1)x + kx² ≥ 1 + (k+1)x. ✓

Therefore (1+x)^k+1 ≥ 1+(k+1)x. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, (1+x)ⁿ ≥ 1+nx for all x ≥ 0 and all integers n ≥ 1.

Step 1 — Base case (n = 4):

2(4)+3 = 11 ≤ 16 = 2⁴. ✓

Step 2 — Inductive hypothesis:

Assume 2k+3 ≤ 2^k for some integer k ≥ 4.

Step 3 — Inductive step: Show 2(k+1)+3 = 2k+5 ≤ 2^k+1.

2^k+1 = 2 × 2^k ≥ 2(2k+3) = 4k+6     [by hypothesis]

Need to show 4k+6 ≥ 2k+5, i.e. 2k ≥ −1. True for all k ≥ 4. ✓

Therefore 2^k+1 ≥ 4k+6 ≥ 2k+5 = 2(k+1)+3. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2n+3 ≤ 2ⁿ for all integers n ≥ 4.

Step 1 — Base case (n = 5):

2⁵ = 32 > 25 = 5². ✓

Note: n=4 gives 2⁴=16=4², which is equality not strict inequality, so n=5 is required.

Step 2 — Inductive hypothesis:

Assume 2^k > k² for some integer k ≥ 5.

Step 3 — Inductive step: Show 2^k+1 > (k+1)².

2^k+1 = 2 × 2^k > 2k²     [by hypothesis]

Need to show 2k² > (k+1)² = k²+2k+1, i.e. k²−2k−1 > 0.

Note k²−2k−1 = (k−1)²−2. For k ≥ 5: k−1 ≥ 4, so (k−1)² ≥ 16 > 2, giving k²−2k−1 > 0. ✓

Therefore 2^k+1 > 2k² > (k+1)². ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2ⁿ > n² for all integers n ≥ 5.

Let S(n) = ∑_k=1ⁿ 1/k² = 1/1² + 1/2² + … + 1/n².

Step 1 — Base case (n = 1):

S(1) = 1/1 = 1 ≤ 2−1 = 1. ✓ (equality holds)

Step 2 — Inductive hypothesis:

Assume S(k) ≤ 2 − 1/k for some integer k ≥ 1.

Step 3 — Inductive step: Show S(k+1) ≤ 2 − 1/(k+1).

S(k+1) = S(k) + 1/(k+1)² ≤ (2 − 1/k) + 1/(k+1)²     [by hypothesis]

It suffices to show: (2 − 1/k) + 1/(k+1)² ≤ 2 − 1/(k+1)

Subtracting 2 from both sides: −1/k + 1/(k+1)² ≤ −1/(k+1)

Rearranging: 1/(k+1)² ≤ 1/k − 1/(k+1)

The right side: 1/k − 1/(k+1) = [(k+1) − k] / [k(k+1)] = 1/[k(k+1)]

So we need: 1/(k+1)² ≤ 1/[k(k+1)], i.e. k(k+1) ≤ (k+1)²

Dividing by (k+1) > 0: k ≤ k+1. This is always true. ✓

Therefore S(k+1) ≤ 2 − 1/(k+1). ✓

Step 4 — Conclusion:

By the principle of mathematical induction, ∑_k=1ⁿ 1/k² ≤ 2 − 1/n for all integers n ≥ 1.