To prove that $n^2 < 3^n$ for all $n \in \{0, 1, 2, 3, \dots \}$, we can approach this problem using mathematical induction. Here's a step-by-step proof:

Step 1: Base case

We first check if the inequality holds for small values of $n$.

• For $n = 0$: $n^2 = 0^2 = 0, \quad 3^n = 3^0 = 1$ Clearly, $0 < 1$, so the inequality holds for $n = 0$.

• For $n = 1$: $n^2 = 1^2 = 1, \quad 3^n = 3^1 = 3$ Clearly, $1 < 3$, so the inequality holds for $n = 1$.

• For $n = 2$: $n^2 = 2^2 = 4, \quad 3^n = 3^2 = 9$ Clearly, $4 < 9$, so the inequality holds for $n = 2$.

• For $n = 3$: $n^2 = 3^2 = 9, \quad 3^n = 3^3 = 27$ Clearly, $9 < 27$, so the inequality holds for $n = 3$.

Thus, the base cases $n = 0, 1, 2, 3$ are true.

Step 2: Inductive step

We assume that the inequality holds for some arbitrary $n = k$. That is, we assume: $k^2 < 3^k$ This is called the inductive hypothesis.

Now, we must prove that the inequality also holds for $n = k + 1$. In other words, we need to show: $(k + 1)^2 < 3^{k+1}$

Expand both sides:

• The left-hand side: $(k + 1)^2 = k^2 + 2k + 1$

• The right-hand side: $3^{k+1} = 3 \cdot 3^k$

Thus, we need to prove that: $k^2 + 2k + 1 < 3 \cdot 3^k$

Using the inductive hypothesis:

Since we know that $k^2 < 3^k$, we can replace $k^2$ with a smaller value: $k^2 + 2k + 1 < 3^k + 2k + 1$ So, now we need to show that: $3^k + 2k + 1 < 3 \cdot 3^k$

Simplifying the right-hand side: $3 \cdot 3^k = 3^k + 2 \cdot 3^k$ Thus, we need to show: $3^k + 2k + 1 < 3^k + 2 \cdot 3^k$

Now, cancel $3^k$ from both sides: $2k + 1 < 2 \cdot 3^k$

Since $3^k$ grows exponentially, it is easy to verify that $2k + 1 < 2 \cdot 3^k$ for all $k \geq 3$. Therefore, the inequality holds for $n = k + 1$.

Step 3: Conclusion

By the principle of mathematical induction, we have shown that $n^2 < 3^n$ for all $n \geq 0$.

---

Would you like more details on any step, or have any questions?

Here are some related questions to explore:

1. How can we prove that $2^n > n^3$ for large $n$?
2. What other methods could be used to compare exponential and polynomial growth?
3. How does $n^2$ compare with $4^n$ as $n$ increases?
4. What are some practical applications of comparing polynomial and exponential growth?
5. Can we establish bounds for the smallest $n$ where $n^2 \geq 3^n$?

Tip: Induction is a powerful tool to prove statements about all natural numbers, especially when dealing with inequalities that involve sequences or recursive relationships.