# Induction for $3^n\geq n^2$ [duplicate]

I need to prove by induction that $3^n\geq n^2$

What I have so far:

1. Basis: $n = 1 \rightarrow 3^1 \geq 1^2 \rightarrow 3 \geq 1$

2. Condition: $3^n\geq n^2$

3. Assumption: $3^{n+1}\geq (n+1)^2$

4. Basis: $3^n\geq n^2$

$3^{n+1}\geq (n+1)^2 = 3(3^n) \geq n^2+2n+1$

That's where I got stuck. I have no idea how to continue from there.

Hint: For $n\geq 2$ we have $3n^2-(n+1)^2=2n^2-2n-1=(n^2-2)+(n-1)^2\ge0$.

Hint:

You can use the condition in your inductive step. In other words, as long as you find an $3^n ≥ n^2$ in the inductive step, you can complete the induction.

We obtained this $3^{n+1}=3.3^n\geq 3n^2$ so far. Now it's enough to prove $3n^2\geq n^2+2n+1$ or $2n^2-2n-1\geq 0$. This inequality holds for $n\geq (1+\sqrt{3})/2$. These two inequalities imply $3^{n+1}\geq (n+1)^2$ for $n\geq 2$.

We verify that it holds for $n=2$ since $3^2\ge2^2$

We assume that it holds for $n:$ $3^n\ge n^2(*)$ and we want to show that $3^{n+1}\ge(n+1)^2$

From $(*)$ we have by multiplying with $3$:

$3^{n+1}\ge3n^2$

But

$3n^2\ge(n+1)^2$ since $3n^2-(n+1)^2=2n^2-2n-2=n^2-2+(n-1)^2\ge0$

Since $n^2-2\ge0, (n-1)^2\gt0$ $\forall n\ge2$

Let me begin with some comments regarding your use of terminology and notation. (These may seem picky, but ultimately, I hope, they'll help you organize your thoughts when you go to write up proofs.)

Regarding notation, the equal sign in "$3^{n+1}\ge(n+1)^2=3(3^n)\ge n^2+2n+1$" is inappropriate. It's fairly clear that what you mean is "$3^{n+1}\ge(n+1)^2$ implies $3(3^n)\ge n^2+2n+1$," so if you want to use a math symbol, you should write "$3^{n+1}\ge(n+1)^2\implies3(3^n)\ge n^2+2n+1$." (I used to see calculus students solve max-min problems by writing things like

$$f(x)=x^2+2x=f'(x)=2x+2=0=x=-1$$ Misuse of the equal sign can be acceptable in rapid scratchwork, but it should be avoided in more formal settings.)

Regarding terminology, "Basis" and "Condition" are OK, although "Base case" and "Inductive hypothesis" would probably be better. But "Assumption" is the wrong term: You're not assuming the inequality $3^{n+1}\ge(n+1)^2$, you're trying to prove it. So in particular, starting with the assertion "$3^{n+1}\ge(n+1)^2=3(3^n)\ge n^2+2n+1$" (even if you replace the "$=$" with a "$\implies$") is inappropriate. What you can say here is $3^{n+1}=3(3^n)\ge3(n^2)$, because that inequality uses the "condition" (aka "inductive hypothesis") $3^n\ge n^2$.

Finally we get to a subtle wrinkle in the proof. What you'd like to say is

$$3^{n+1}=3(3^n)\ge3n^2=n^2+n^2+n^2\ge n^2+2n+1=(n+1)^2$$

using the "obvious" facts that $n^2\ge2n$ and $n^2\ge1$. But your base case only establishes that $3^n\ge n^2$ for $n=1$, and the "obvious" inequality $n^2\ge2n$ is not true for $n=1$. To make this proof work, you need to establish two base cases, namely $3^1\ge1^2$ and $3^2\ge2^2$. (Technically speaking, $n=2$ is the base case for the induction; checking the case $n=1$ is needed in order to prove the inequality is true for all positive integers.)

Sorry if this is a bit longwinded, but careful attention to mathematical niceties when you're first learning to write proofs pays off in the long run.

• Thanks :) Yes, I know that my terminology is off. My calculus course is not in English and it has been a while since the last time I had to do it in English. And since I wanted to post the question before my appointment I did not look it up. But I did manage to complete the proof with these hints. – Willi Oct 27 '17 at 15:21
• @Willi, I'm glad it helped. Technical terms aside, your English reads very well. – Barry Cipra Oct 27 '17 at 15:54