Show that, ∀n∈ℕ, 3^n > n^2.
We want to prove that
$$ \forall n \in \mathbb{N},\quad 3^n > n^2. $$
Step 1: Check small values of $n$
Let’s test a few small values to see when this inequality starts to hold:
- $n = 1$: $3^1 = 3 > 1^2 = 1$ ✅
- $n = 2$: $3^2 = 9 > 2^2 = 4$ ✅
- $n = 3$: $3^3 = 27 > 9$ ✅
- $n = 4$: $3^4 = 81 > 16$ ✅
- $n = 5$: $3^5 = 243 > 25$ ✅
So far, $3^n > n^2$ for all $n = 1, 2, 3, 4, 5$. Now let’s prove this by induction.
Step 2: Mathematical Induction
Base Case: $n = 1$
$$ 3^1 = 3 > 1^2 = 1 \quad \text{✔️} $$
Inductive Hypothesis:
Assume for some $k \ge 1$, the inequality holds:
$$ 3^k > k^2 $$
Inductive Step: Show $3^{k+1} > (k+1)^2$
Starting from the LHS:
$$ 3^{k+1} = 3 \cdot 3^k $$
Using the inductive hypothesis $3^k > k^2$, we get:
$$ 3^{k+1} = 3 \cdot 3^k > 3 \cdot k^2 $$
So if we can show:
$$ 3k^2 > (k+1)^2 = k^2 + 2k + 1 $$
then the inductive step will be complete.
Let’s prove that:
$$ 3k^2 > k^2 + 2k + 1 \Rightarrow 3k^2 - (k^2 + 2k + 1) = 2k^2 - 2k - 1 > 0 $$
Now check when $2k^2 - 2k - 1 > 0$. This is a quadratic in $k$. Solve:
$$ 2k^2 - 2k - 1 = 0 \Rightarrow k = \frac{2 \pm \sqrt{(-2)^2 + 8}}{4} = \frac{2 \pm \sqrt{12}}{4} = \frac{2 \pm 2\sqrt{3}}{4} = \frac{1 \pm \sqrt{3}}{2} $$
So the inequality $2k^2 - 2k - 1 > 0$ holds when
$$ k > \frac{1 + \sqrt{3}}{2} \approx 1.366 $$
Thus, for $k \ge 2$, the inequality is certainly true.
Step 3: Adjust the Domain
The inequality holds for all $n \ge 1$, and the inductive step is valid for $k \ge 2$. But:
- Base cases $n = 1$ and $n = 2$: already checked and true.
- Inductive step works from $k = 2$ onward.
So we can conclude:
✅ Final Answer:
$$ \boxed{\forall n \in \mathbb{N},\, n \ge 1,\quad 3^n > n^2} $$
If you define $\mathbb{N}$ to include 0, then at $n = 0$, $3^0 = 1 > 0^2 = 0$, so it still holds. Thus:
$$ \boxed{\forall n \in \mathbb{N},\quad 3^n > n^2} $$
No comments:
Post a Comment