4
$\begingroup$

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

I am using induction and I understand that when $n=1$ it is true. The induction hypothesis is when $n=k$ so $3^k>k^2$. So for the induction step we have $n=k+1$ so $3^{k+1} > (k+1)^2$ which is equal to $3\cdot3^k > k^2+2k+1$. I know you multiple both sides of the induction hypothesis by $3$ but I'm not sure what to do next.

$\endgroup$
1
$\begingroup$

Let's leave aside the base step, for the moment.

Suppose the inequality holds for $n=k$; then $$ 3^{k+1}=3\cdot 3^k>3k^2=k^2+2k+1+2k^2-2k-1=(k+1)^2+(2k^2-2k-1) $$ The induction hypothesis has been applied at the first $>$ sign.

We have $2k^2-2k-1>0$ as soon as $k\ge2$. Indeed, $2x^2-2x-1<0$ if and only if $(1-\sqrt{3})/2<x<(1+\sqrt{3})/2$ and $1<(1+\sqrt{3})/2<2$.

Here the base step is $n=2$, not $n=1$, but of course the inequality holds also for $n=1$.

$\endgroup$
1
$\begingroup$

$3^{n + 1} = 3 * 3^n > 3 n^2 > (n + 1)^2$ for sufficiently large $n$. The hypothesis that $3^n > n^2$ is used for the first inequality, and you can probably figure out what "sufficiently large $n$" is for the last step.

The $3n^2 > (n + 1)^2$ inequality might seem suspicious. One way to see that it will be valid for sufficiently large $n$ is to consider the order of growth of both sides of the inequality. Both sides are quadratic and in particular, for sufficiently large $n$, the $n^2$ term of $(n + 1)^2 = n^2 + 2n + 1$ will "dominate" the other terms. At that point we'll have $(n + 1)^2 = n^2 + 2n + 1\approx n^2 < 3n^2$, but maybe that's a little too hand wavy right now. Another way to see it is to note that $3n^2 > (n + 1)^2$ is equivalent to $n^2 - 2n - 1 > 0$:

\begin{align} 3n^2 &> (n + 1)^2\\ 3n^2 - (n + 1)^2 &> 0\\ 3n^2 - 2n^2 - 2n - 1 &> 0\\ n^2 - 2n - 1 &> 0 \end{align}

and you can solve $n^2 - 2n - 1 > 0$ using the quadratic equation. You'll find that $n > \frac{1}{2}(1+\sqrt{3})$ (or $n < \frac{1}{2}(1-\sqrt{3})$, but the negative solution isn't relevant here). Since $\frac{1}{2}(1+\sqrt{3})\approx 1.366<2$ the argument that uses $3n^2>(n+1)^2$ applies for $n = 2, 3,$ etc. If instead we had found that "sufficiently large $n$" meant $n > N \geq 2$ then we would have had to check additional base cases, $n = 2, 3, \ldots, N$ in order to complete the proof.

As an aside, I get the impression that you are thinking of proof by induction as a kind of mechanical process: "The induction hypothesis is when $n=k$", "I know you multiply both sides of the induction hypothesis by $3$", etc. It doesn't have to be so mechanical. For example, notice that "$k$" doesn't even appear in the steps above. This isn't meant as a criticism, just something to be aware of as you develop your skills.

$\endgroup$
  • $\begingroup$ How did you get (n+1)^2 after >. where is the math in this? $\endgroup$ – bella Nov 10 '15 at 5:20
  • $\begingroup$ @bella: Good question, I'll add a little about that to my answer. $\endgroup$ – Aaron Golden Nov 10 '15 at 7:22
0
$\begingroup$

You start with knowing that $3^k > k^2$ and you prove that if you know that then you prove that $3^{k+1} > (k+1)^2$.

One straightforward and Doy! way is to note:

$3^k > k^2$

$3^k + 3^k + 3^k> k^2 + k^2+k^2$.

Since $k \ge 2$ then $k^2 \ge 2k$ and as $k \ge 2$ then $k^2 > 1$

So

$3^k + 3^k + 3^k > k^2 + 2k + 1$

$3^{k+1} = 3*3^k > (k+1)^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.