1

Prove by induction that $3^n > n^2$

I tried to prove this but I finally got to a point from where I could not proceed any further. I tested this and this relation seems to be true for all $n \in \mathbb N$.

(1) The first step: $3^1 > 1^2$, the inequality holds.
(2) I assume that this relation inequality holds for all natural numbers smaller than or equal to some $k$, and so $3^k > k^2$
(3) The inductive step:
$$3^{k+1} =3 \cdot 3^k > 3k^2 =k^2 + k^2 + k^2$$ This would be great if I could show that $k^2+k^2 > 2k +1$ for all natural numbers. Unfortunately, this is simply not the case for $n=1$, because $2 < 3$. And so my idea does not work. Is there an alternative way to tackle this problem?

Aemilius
  • 3,699
  • For $n=1$ you have shown it already, see $(1)$. – Dietrich Burde Nov 22 '17 at 21:09
  • The base case should be $n=2$. Then, your analysis works for $k\ge 2$. And incidentally, $3^1>1^2$ also. So, the inequality is correct for all natural numbers. – Mark Viola Nov 22 '17 at 21:16
  • Adding second base case $n=2$ is perfectly acceptable. However you do not need to, as $33^k$ is strictly* greater than $3k^2$ you don't* have to show that $k^2 + k^2$ is strictly greater than $2k+1$; only that it is greater or equal to $2k+1$. – fleablood Nov 22 '17 at 21:26
  • Oh, wait. $k^2 + k^2 < 2k + 1$ if $k = 1$. ... oh well, A second base case is fine. – fleablood Nov 22 '17 at 22:13

1 Answers1

1

"This would be great if I could show that $k^2+k^2>2k+1$ for all natural numbers."

That would be great. But as $3^{k+1} > k^2+ k^2+k^2$. You actually only have to show that $k^2 + k^2 \ge 2k + 1$ for all natural numbers. (i.e. $3^{k+1} = 3*3^{k} > 3*k^2 = k^2 + k^2 + k^2 \ge k^2 + 2k + 1$)

Which you've certainly demonstrated you are capable of doing.

=====

BTW. There is nothing wrong when you hit a localized snag with, breaking into specific and general cases. Example:

"If $k \ge 2$ then $k^2 + k^2 > 2k + 1$. And if $k = 1$ then $k+1 = 2$ and $3^2 > 2^2$."

Absolutely nothing wrong with that.

fleablood
  • 124,253
  • Hmmph... actually I was wrong. $k^2 + k^2 \not \ge 2k+1$ for $k=1$. (D'oh!) ... so second base case is fine. – fleablood Nov 22 '17 at 22:19