Homework Help: Induction Proof that 2^n > n^2 for n>=5

For induction, you have to prove the base case. Then you assume your induction hypothesis, which in this case is 2ⁿ >= n². After that you want to prove that it is true for n + 1, i.e. that 2ⁿ⁺¹ >= (n+1)². You will use the induction hypothesis in the proof (the assumption that 2ⁿ >= n²).

 

You know that [tex]2^{n} \geq 2n+1[/tex] for [tex]n \geq 5[/tex]. Follow Steelphantoms template for an inductive proof and take it to home plate.

 

No, Dylanette's point was that you KNOW "[itex]2^k\ge 2k+1[/itex]" for some k and now want to prove that [itex]2^{k+1}\ge 2(k+1)+ 1[/itex]". (I prefer to use "k" rather than "n" again just to avoid this kind of confusion.)

If [itex]2^k\ge 2k+1[/itex], then [itex]2^{k+1}= 2(2^k)\ge 2(2k+ 1)= 4k+ 2[/itex].
Since you want 2(k+ 1)+ 1= 2k+ 3, try rewriting that "4k": 4k+ 2= 2k+ 2+ 2k so you need to be able to say "[itex]2k\ge 1[/itex]". That's pretty obvious, isn't it?

 

Halls, re-read his original problem, he has to prove that [tex]2^{k+1} \ge (k+1)^2 [/tex] assuming that [tex]2^k \ge k^2[/tex]

 

Okay, I reread his post. What he said was "I got to the point where I just need to prove [itex]2^n \ge 2n+ 1[/itex] by induction also".

 

oops, I should take my own advice, my bad.

 

what does RHS stand for? "added to factor the RHS"

 

RHS=Right Hand Side (of the equation).

 

im super stuck. don't know how to get to the 2^n > 2n+1 step that the posters are talking about. I know I have to use 2^k=k^2 and also that 2^k+1 = 2(2^k).

 

It's not clear to me either (now, five months after the original post). I arrive at a different point to complete the proof.

You want to show that [itex]2^x\ge x^2[/itex] for [itex]x\ge 5[/itex].

First, when x= 5, 2⁵= 32> 25= 5² so it is true for x= 5. Now, suppose [itex]2^k\ge k^2[/itex] for some k. We need to show that it follows that [itex]2^{k+1}\ge (k+ 1)^2[/itex]. As you say, [itex]2^{k+1}= 2(2^k)\ge 2(k^2)[/itex]. The proof will be complete if we can show that [itex]2k^2\ge (k+ 1)^2[/itex], for [itex]k\ge 5[/itex]. A little algebra show that is equivalent to proving that [itex](k-1)^2\ge 2[/itex] which is certainly true for [itex]k\ge 5[/itex]

 

Notice that as long as [tex] k \ge 5 [/tex] it is true that

[tex]
k^2 > 2k+1
[/tex]

(examine the parabola [tex] k^2 - 2k - 1 [/tex] to see this)

The induction anchor is that [tex] 2^k \ge k^2 [/tex] for some [tex] k \ge 5 [/tex]. Then

[tex]
\begin{align*}
2^{k+1} & = 2 \left(2^k\right) \ge 2\left(k^2\right)\\
& = 2k^2 = k^2 + k^2\\
& > k^2 + 2k + 1 \tag{From earlier point}\\
& = (k+1)^2 \\
\intertext{Therefore}
2^{k+1} \ge (k+1)^2
\end{align*}
[/tex]

 

hi . If possible, please explain why :

k^2 > 2k +1

I dont understand it .

 

As statdad said, look at [itex]y= k^2- 2k- 1= k^2- 2k+ 1- 2= (k+1)^2-2[/itex]. The graph of that is a parabola with vertex at (-1, -2). For x> -1 y is increasing and when x= 2, [itex]y= (5-1)^2- 2= 14> 0[/itex]. So for k> 5, [itex]k^2- 2k- 1> 0[/itex] and thus [itex]k^2> 2k+ 1[/itex].

 

thank you very much