Friday, July 11, 2025

Proof ∀n>4, 2^n > n^2

Use induction to prove that ∀n>4, 2^n > n^2.

We want to prove by mathematical induction that:

$$ \forall n > 4,\quad 2^n > n^2 $$


Step 1: Base Case

Let $n = 5$. We need to check whether the inequality holds:

$$ 2^5 = 32,\quad 5^2 = 25,\quad \text{and} \quad 32 > 25 $$

Base case holds.


Step 2: Inductive Hypothesis

Assume that the statement is true for some integer $k \geq 5$. That is, assume:

$$ 2^k > k^2 $$

This is our inductive hypothesis.


Step 3: Inductive Step

We must show that this implies:

$$ 2^{k+1} > (k+1)^2 $$

Start with:

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

Using the inductive hypothesis $2^k > k^2$, we get:

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

So we want to show:

$$ 2k^2 > (k+1)^2 $$

Expand the right-hand side:

$$ (k+1)^2 = k^2 + 2k + 1 $$

So we want:

$$ 2k^2 > k^2 + 2k + 1 $$

Subtract $k^2 + 2k + 1$ from both sides:

$$ 2k^2 - (k^2 + 2k + 1) = k^2 - 2k - 1 > 0 $$

We now solve:

$$ k^2 - 2k - 1 > 0 $$

Find the roots of $k^2 - 2k - 1 = 0$:

$$ k = \frac{2 \pm \sqrt{4 + 4}}{2} = \frac{2 \pm \sqrt{8}}{2} = \frac{2 \pm 2\sqrt{2}}{2} = 1 \pm \sqrt{2} $$

So $k^2 - 2k - 1 > 0$ for $k > 1 + \sqrt{2} \approx 2.41$

✅ Since we assume $k \geq 5$, the inequality holds.


Conclusion

By mathematical induction, we have shown that:

$$ \forall n > 4,\quad 2^n > n^2 $$

Proved.

No comments:

Post a Comment