Skip to main content

Induction: n < 2^n

Short answer

Base case n=1: 1<2 holds. Assume k < 2^k. Then k+1 < 2^k + 1 ≤ 2^k + 2^k = 2^(k+1). Thus by mathematical induction, n < 2^n for all positive integers n.

Use mathematical induction to prove the inequality n < 2^n for all positive integers n.

To prove. P(n): n < 2ⁿ for all positive integers n.

Basis step (n = 1)

1 < 2¹ = 2, which is true. So P(1) holds.

Inductive hypothesis

Assume P(k) is true for some k ≥ 1: k < 2ᵏ.

Inductive step

Show P(k+1): k + 1 < 2ᵏ⁺¹.

  1. From the hypothesis, k < 2ᵏ. Add 1 to both sides: k + 1 < 2ᵏ + 1.
  2. Since k ≥ 1, 2ᵏ ≥ 2 > 1, so 1 < 2ᵏ, giving 2ᵏ + 1 < 2ᵏ + 2ᵏ.
  3. Therefore k + 1 < 2ᵏ + 2ᵏ = 2·2ᵏ = 2ᵏ⁺¹.

So P(k+1) is true.

Conclusion

By mathematical induction, n < 2ⁿ for every positive integer n. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 1 questions →