Prove 2^n > n for all positive integers

Question

Prove by the Principle of Mathematical Induction that $2^n > n$ for all positive integers $n$ .

Solution — Step by Step

Let $P(n)$ : $2^n > n$ , for all positive integers $n \geq 1$ .

Base case ( $n = 1$ ): $2^1 = 2 > 1$ . ✓

$P(1)$ is true.

Inductive hypothesis: Assume $P(k)$ is true for some arbitrary positive integer $k \geq 1$ .

That is, assume: $2^k > k$ … (1)

We need to prove that $P(k+1)$ is also true, i.e., that $2^{k+1} > k+1$ .

Starting from the left side of what we want to prove:

2^{k+1} = 2 \cdot 2^k

From the inductive hypothesis (1): $2^k > k$ , so $2 \cdot 2^k > 2k$ .

Therefore:

2^{k+1} > 2k

Now, for positive integers $k \geq 1$ : is $2k \geq k+1$ ?

$2k \geq k+1 \iff k \geq 1$ ✓ (this is true by our assumption)

Therefore: $2^{k+1} > 2k \geq k+1$

\boxed{2^{k+1} > k+1}

$P(k+1)$ is true.

We have shown:

$P(1)$ is true (base case)
If $P(k)$ is true, then $P(k+1)$ is true (inductive step)

By the Principle of Mathematical Induction, $P(n)$ is true for all positive integers $n$ .

Hence, $2^n > n$ for all $n \in \mathbb{N}$ . $\blacksquare$

Why This Works

Mathematical induction works like an infinite chain of dominoes. We show the first domino falls (base case). We show each domino knocks over the next (inductive step). Therefore, all dominoes fall.

The key insight here is that $2^{k+1} = 2 \times 2^k$ . By multiplying the LHS by 2, we get something much larger than $k+1$ — in fact, larger than $2k$ , and $2k \geq k+1$ for all $k \geq 1$ . This is the “engine” that drives the inequality forward.

The inequality $2k \geq k+1$ is equivalent to $k \geq 1$ , which is always satisfied in our induction (since $k$ is a positive integer). This is why we need $k \geq 1$ specified in the hypothesis.

Alternative Method — Direct Verification

While induction is the required method, you can verify for small values to build intuition:

$n$	$2^n$	$n$	$2^n > n$ ?
1	2	1	Yes
2	4	2	Yes
3	8	3	Yes
10	1024	10	Yes
20	1,048,576	20	Yes

Exponential growth ( $2^n$ ) vs linear growth ( $n$ ) — the exponential always wins, and the gap gets larger.

Common Mistake

Skipping the step that justifies $2k \geq k+1$ . Students write " $2^{k+1} = 2 \cdot 2^k > 2k > k+1$ " without showing WHY $2k > k+1$ . This step needs justification: $2k - k - 1 = k - 1 \geq 0$ for $k \geq 1$ . Without this, the proof has a gap and loses marks in boards.

Question

Solution — Step by Step

Why This Works

Alternative Method — Direct Verification

Common Mistake

Try These Next