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