0

Question: Prove $2^n > n^2$ for $n > 4$

Going to fast forward to my problem so:

Base case: $n = 5$ true

Induction step:

Suppose true for $n = k > 4$ true, i.e. $2^k > k^2$. Now consider $n = k+1$:

$$\begin{align} 2^{k+1} &= 2(2^k) \\ &> 2(k^2) &\text{(from supposition)} \\ &= k^2 + k^2 \\ &> k^2 + 2k + 1 &\color{red}{\text{(since }k^2 > 2k + 1\text{)}} \\ &= (k+1)^2 \end{align}$$

Hence true for $n = k+1$.

For the claim in red, how do I go about showing this? I can either do it: graphically, or algebraically (i.e. consider the derivatives of $y = k^2$ and $y = 2k+1$ and show that one grows faster), or redefine my whole approach to the question. I'm unsure about these little details :(

user642796
  • 52,188
Aean
  • 113

2 Answers2

2

First Method: Since this is a problem of induction, why not. Use induction ;)

Second Method: You need to prove that $k^2-2k-1 >0$. Factor the left hand side and observe that both roots are less than $5$. Find the sign of the quadratic.

Third method (fastest, and easy, but tricky to find):

As $k \geq 5$ we have

$$k^2 \geq 5k =2k+3k >2k+1 \,.$$

Fourth Method

$$k^2 >2k+1 \Leftrightarrow k^2-2k+1 >2 \Leftrightarrow (k-1)^2 >2$$

Now, since $k\geq 5$ we have $k-1\geq 4$ and hence $(k-1)^2 \geq 4^2 >2$.

N. S.
  • 132,525
  • First method would be too long right? (Induction within induction lol) – Aean Oct 19 '13 at 03:44
  • Second method: It looks lengthy in my proof (since it involves use of quadratic formula and stuff). If I were to use this method, do I just write it up on the side of my paper and say "since -->" – Aean Oct 19 '13 at 03:49
  • Third method: But how do you know k^2 > 5k? I know it is obvious/intuitive but don't I have to do some sought of rigorous proof such as when k = 5, k^2 >= 5k and then consider their derivatives i.e. 2k > 5 and hence k^2 >= 5k true for all k>=5? – Aean Oct 19 '13 at 03:50
  • 1
    For your troubles with the third method, notice that $k \geq 5$ then $k \cdot k \geq 5 \cdot k$. It could be that the two sides of the inequality were equal, but it could certainly also be that the LHS was larger than the RHS, do you see? This is enough proof in and of itself, simply by the properties of the integers. – Numbersandsoon Oct 19 '13 at 03:58
  • Ohh that makes sense; can't believe I didn't see that. Thank you!! – Aean Oct 19 '13 at 04:00
  • @Aean Added one more, is basically the same as the second method, but instead of using the quadratic formula you just complete the square, and you are done. – N. S. Oct 19 '13 at 04:55
1

You want to prove $2k^2 > k^2 + 2k + 1 = (k+1)^2$. Try to assume that this isn't true. Then we must have $2k^2 \leq k^2 +2k +1$ or $k^2 \leq 2k+1$. Rewrite this to give $$k^2 -1 \leq 2k$$ or $$(k-1)(k+1) \leq 2k.$$ Since $(k+1) > k$ and $(k-1) > 3$, we get a contradiction. Thus, $2k^2 > (k+1)^2$.

Numbersandsoon
  • 2,910
  • But how do I put this in my proof? Do I do it on the side or something? I just need to know how to layout my work and that's all my question really is. What does everyone else do? – Aean Oct 19 '13 at 03:52
  • 1
    You could make a break in the induction proof after $2^{k+1} > 2k^2$ and say "We claim that $2k^2 > (k+1)^2$. Proof: Suppose that $2k^2 \leq (k+1)^2$. Then... Therefore, $2k^2 > (k+1)^2$. By the principle of mathematical induction, $2^n > n^2$ for $n > 4$." Or something along those lines. Remember to add in your proof that $n,k$ etc. are integers, i.e. belong in $\mathbb{Z}$. – Numbersandsoon Oct 19 '13 at 03:56
  • Thank you :) You have helped cleared a lot of my troubles when setting out my proofs. – Aean Oct 19 '13 at 04:01