We are tasked with proving that $n^2 < 3^n$ for all natural numbers $n \in \{0, 1, 2, 3, \dots\}$ using mathematical induction.

Step 1: Base Case ( $n = 0$ )

We start by checking the inequality for $n = 0$:

$0^2 = 0 \quad \text{and} \quad 3^0 = 1.$

Clearly, $0 < 1$, so the inequality holds for $n = 0$.

Step 2: Inductive Hypothesis

Assume the inequality holds for some arbitrary $n = k$. That is, we assume:

$k^2 < 3^k$

for some $k \geq 0$.

Step 3: Inductive Step

We must now prove that the inequality also holds for $n = k + 1$. That is, we need to show:

$(k+1)^2 < 3^{k+1}.$

Expanding both sides:

The left-hand side is:

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

The right-hand side is:

$3^{k+1} = 3 \cdot 3^k.$

Thus, we want to prove:

$k^2 + 2k + 1 < 3 \cdot 3^k.$

Using the inductive hypothesis:

From the inductive hypothesis, we know that $k^2 < 3^k$, so we can replace $k^2$ with something smaller in the inequality:

$k^2 + 2k + 1 < 3^k + 2k + 1.$

Thus, it remains to prove:

$3^k + 2k + 1 < 3 \cdot 3^k.$

Simplifying the right-hand side:

$3^k + 2k + 1 < 3^{k+1}.$

This inequality holds if $2k + 1 < 2 \cdot 3^k$, or equivalently:

$2k + 1 < 2 \cdot 3^k.$

Verifying $2k + 1 < 2 \cdot 3^k$ for $k \geq 1$:

For $k = 1$:

$2(1) + 1 = 3 \quad \text{and} \quad 2 \cdot 3^1 = 6.$ Clearly, $3 < 6$.

For $k = 2$:

$2(2) + 1 = 5 \quad \text{and} \quad 2 \cdot 3^2 = 18.$ Clearly, $5 < 18$.

For $k \geq 1$, as $k$ grows, $2 \cdot 3^k$ grows much faster than $2k + 1$, so the inequality $2k + 1 < 2 \cdot 3^k$ holds for all $k \geq 1$.

Conclusion:

By the principle of mathematical induction, the inequality $n^2 < 3^n$ holds for all $n \in \{0, 1, 2, 3, \dots\}$.

---

Do you want more details on any specific step? Here are 5 relative questions:

1. Why does the inductive step work in mathematical induction?
2. What is the importance of base cases in induction?
3. How can we adjust inductive proofs for inequalities with different functions?
4. What is the difference between strong induction and regular induction?
5. How does the growth rate of exponential functions compare to polynomials?

Tip: In induction proofs, always check the smallest values to ensure the inequality holds at those critical early steps.