Prove $ 3^n>n^2-1 $

Question

In the base case $n=0$ it's obvious that the equation holds. So, the induction hypothesis is that $3^n>n^2-1$.

The next step is of course $3^{n+1}>(n+1)^2-1=n^2+2n$

Using our assumption we have: $3^{n+1}>3n^2-3$ And I have to show that right part of this inequality is equal the right part of upper inequality.

Below is showed my process of thinking.

\begin{equation} 3^{n+1}>3n^2-3=2n^2+n\cdot n-3>2n^2+n-3 \end{equation}

And in the similar way we have the final result:

\begin{equation} 3^{n+1}>n^2+2n-3 \end{equation}

I have skipped some description and finer points but this is only sketch of a proof. In according to my process of thinking. I removed one of a $n$ in this $ n\cdot n $ by knowing that $n=1$ satisfies my inequality so I can shuffle it off knowing that the left side will be greater.

My question is how to get rid of this $-3$?

Answer 1

You are trying to show $3n^2-3>(n+1)^2-1$. Your estimation failed because you did a very coarse estimation $n\cdot n>n$ twice!

Try the estimation $n^2>Cn$, where $C$ can be any constant you want.

Answer 2

The induction hypothesis is that $3^n>n^2-1$. You then want to show that $$3^{n+1}>(n+1)^2-1.$$ Indeed you can expand the right hand side to see that it suffices to show that $$3^{n+1}>n^2+2n.$$ Then a bit of rearrangement shows that this is equivalent to $$3\cdot3^n>(n^2-1)+(2n+1).$$ Given the induction hypothesis, this is equivalent to $$3\cdot3^n>3^n+2n+1.$$ And a bit more rearranging shows that this is equivalent to $$3^n>\tfrac{n+1}{2}.$$ Now you have a linear function of $n$ on the right hand side, instead of a quadratic. Can you prove this inequality by induction?