# Induction on $2^n > n^2 - 7$.

I am trying to prove, by induction, that $2^n > n^2 - 7, \forall n \in \mathbb{N}$.

I am stuck in the inductive step: $n = n+1$.

\begin{align*} 2^{n+1} &= 2 \cdot 2^n \\ &> 2 \cdot (n^2 - 7) \tag{By I.H.} \\ &= 2 \cdot (n^2 + 2n + 1 - 10) \\ &= 2(n+1)^2 - 20 \\ &> (n+1)^2 - 17 \end{align*}

Which is not what I want, $(n+1)^2 - 7$. I'm not seeing how to reduce the constant to 7, any hints appreciated.

• The title says $\gt$ but you are proving $\lt$ ? – A---B Feb 19 '17 at 3:25
• $2(n^2-7)\ge(n+1)^2-7$ for $n > 3$, and you can solve it by hand for $n \le 3$. – didgogns Feb 19 '17 at 3:26
• A stronger inequality is $2^n>n^2-2$ (for all $n\in\mathbb{N}). – Adren Feb 19 '17 at 5:45 • Why does$n^2-7 =n^2+2n+1-10$? – fleablood Feb 19 '17 at 6:09 ## 1 Answer First off,$+1$for an excellent question. Second, you have switched signs ($>$to$<$). You are given that$2^n > n^2-7$,and have to prove it for$n+1$. To do this, note that:$2^{n+1} = 2 \cdot 2^n > 2(n^2-7) > 2n^2 - 14$. Note that$2n^2 - 14 - ((n+1)^2 - 7) = (n+2)(n-4) > 0$if$n \geq 5$. Hence, it follows that$2^{n+1} > 2n^2 - 14 > (n+1)^2 - 7$for$n \geq 5\$. You can check the rest manually (I leave it to you).

Key point : Don't worry if the RHS doesn't immediately suggest a finish to the argument. In this case, I took the difference between the RHS I got, and the RHS I wanted, and the nature of the difference allowed me to deduce the identity for all but a very small set of small numbers, which was easy to do manually.

• Do keep this trick in mind! – Teresa Lisbon Feb 19 '17 at 5:03
• I certainly will. Thank you. – mnk888 Feb 19 '17 at 5:20
• You are welcome @mnk888 – Teresa Lisbon Feb 19 '17 at 5:21