Friday, July 11, 2025

Proof ∀n∈ℕ, 3^n > n^2

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