1

Show that $ n^2 \leq 3^{n-1} $ by mathematical induction.

I set my base case as $n = 1$, and got that $1 \leq 1$.

I assume $n = k$. Then my inductive hypothesis is $ k^2 \leq 3^{k-1} $. So when I check my claim I did: $(k+1)^2 \leq 3^{(k+1)-1}$. But I get lost after this.

1721
  • 45
mathisfun1234
  • 49
  • 1
    The second inequality is what you need to derive from the first. Start by multiplying each side of the inequality by $3$ – Loobear23 May 06 '20 at 15:00

1 Answers1

2

You're on the right track. Again, let's assume $n=k$ for some natural number $k\geq 2$. By our inductive hypothesis, $3^{k-1}\geq k^2,$ or equivalently, $3^k\geq 3k^2.$ From here, we see that

$$ \begin{align} (k+1)^2 &= k^2+2k+1 \\\ &\leq k^2+k^2+k^2 \\\ &=3k^2\leq 3^k. \end{align} $$

This closes induction.

Crosby
  • 585