3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The title says $\gt$ but you are proving $\lt$ ? $\endgroup$ – A---B Feb 19 '17 at 3:25
  • 1
    $\begingroup$ $2(n^2-7)\ge(n+1)^2-7$ for $n > 3$, and you can solve it by hand for $n \le 3$. $\endgroup$ – didgogns Feb 19 '17 at 3:26
  • $\begingroup$ A stronger inequality is $2^n>n^2-2$ (for all $n\in\mathbb{N}). $\endgroup$ – Adren Feb 19 '17 at 5:45
  • $\begingroup$ Why does $n^2-7 =n^2+2n+1-10$? $\endgroup$ – fleablood Feb 19 '17 at 6:09
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Do keep this trick in mind! $\endgroup$ – Teresa Lisbon Feb 19 '17 at 5:03
  • $\begingroup$ I certainly will. Thank you. $\endgroup$ – mnk888 Feb 19 '17 at 5:20
  • $\begingroup$ You are welcome @mnk888 $\endgroup$ – Teresa Lisbon Feb 19 '17 at 5:21

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.