---
title: "Induction: n < 2^n"
subject: "Discrete Structure"
chapter: 1
key: "semester_4/discrete_structure:induction-n-less-than-2-power-n"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/induction-n-less-than-2-power-n
site: BCT Engineering
---

# Induction: n < 2^n

Discrete Structure · Chapter 1: Logic, Induction and Reasoning

- Asked in: 2069 Bhadra, 8 marks
- Video: [Inequality Mathematical Induction Proof: 2^n greater than n^2](https://www.youtube.com/watch?v=0VIIRBLH1WI) — The Math Sorcerer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/induction-n-less-than-2-power-n
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-1

## Question

Use mathematical induction to prove the inequality n < 2^n for all positive integers 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.

## Answer

**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. ∎

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. The basis n = 1 checks?
   A. 1 < 1
   B. 2 < 2
   C. 0 < 1
   D. 1 < 2
   Answer: D. 1 < 2¹ = 2. (Key point: Basis)

2. From k < 2ᵏ, what is done first?
   A. Multiply by k
   B. Subtract 1
   C. Square both sides
   D. Add 1 to both sides: k + 1 < 2ᵏ + 1
   Answer: D. Adding 1 gives the k+1 on the left. (Key point: First move)

3. Why is 1 < 2ᵏ?
   A. 2ᵏ = k
   B. k < 1
   C. 2ᵏ = 1
   D. 2ᵏ ≥ 2 for k ≥ 1
   Answer: D. Because 2ᵏ ≥ 2 > 1 when k ≥ 1. (Key point: Using k ≥ 1)

4. 2ᵏ + 2ᵏ equals?
   A. 2ᵏ⁺²
   B. 4ᵏ
   C. 2ᵏ·k
   D. 2ᵏ⁺¹
   Answer: D. 2·2ᵏ = 2ᵏ⁺¹. (Key point: Closing)

## Related in Discrete Structure

- [Induction: sum of cubes](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-of-cubes) — Discrete Structure, chapter 1, asked 2×
- [Induction: sum of squares](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-of-squares) — Discrete Structure, chapter 1, asked 2×
- [Induction: 3+3·5+3·5²+...+3·5^n](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-3-times-5-powers) — Discrete Structure, chapter 1, asked 2×
- [Induction: sum of geometric progression](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-geometric-series-sum) — Discrete Structure, chapter 1
- [Weak induction; 5^n − 1 divisible by 4](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-5-power-n-minus-1-divisible-4) — Discrete Structure, chapter 1
- [Induction: sum of n(n+1)(n+2)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-product-n-n1-n2) — Discrete Structure, chapter 1

## Related in other subjects

- [Prove positive XOR equals negative XNOR](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Apositive-xor-negative-xnor-prove) — Digital Logic, chapter 2, asked 3×
- [Induction: 5^n − 1 divisible by 4](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-five-power) — Theory of Computation, chapter 1, asked 2×
- [Induction: sum of k·k! = (n+1)!−1](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-factorial-sum) — Theory of Computation, chapter 1, asked 2×
- [Induction: n⁴ − 4n² divisible by 3](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-n4-4n2) — Theory of Computation, chapter 1, asked 2×