• Support PF! Buy your school textbooks, materials and every day products Here!

Induction Proof that 2^n > n^2 for n>=5

  • Thread starter dtl42
  • Start date
  • #1
119
0

Homework Statement


Prove that [tex]2^{x} \geq x^{2}[/tex]
[tex]\forall x\geq5[/tex]


Homework Equations


[tex]2^{k} \geq x^{k}[/tex]


The Attempt at a Solution


I multiplied both sides by 2, then added to factor the RHS, and eventually got to the point where I just need to prove [tex]2^{n} \geq 2n+1[/tex] by induction also.
 

Answers and Replies

  • #2
159
0
For induction, you have to prove the base case. Then you assume your induction hypothesis, which in this case is 2n >= n2. After that you want to prove that it is true for n + 1, i.e. that 2n+1 >= (n+1)2. You will use the induction hypothesis in the proof (the assumption that 2n >= n2).
 
Last edited:
  • #3
5
0
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.
 
  • #4
119
0
How do I know that [tex]
2^{n} \geq 2n+1
[/tex] for
[tex]
n \geq 5
[/tex]

That's what else I need to prove by induction.
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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?
 
  • #6
441
0
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]
 
  • #7
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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".
 
Last edited by a moderator:
  • #8
441
0
:blushing::blushing::blushing:

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

:blushing::blushing::blushing:
 
  • #9
32
0
what does RHS stand for? "added to factor the RHS"
 
  • #10
Dick
Science Advisor
Homework Helper
26,258
618
RHS=Right Hand Side (of the equation).
 
  • #11
32
0
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).
 
  • #12
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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, 25= 32> 25= 52 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]
 
Last edited by a moderator:
  • #13
statdad
Homework Helper
1,495
35
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
& = (k+1)^2 \\
2^{k+1} \ge (k+1)^2
\end{align*}
[/tex]
 
Last edited by a moderator:
  • #14
2
0
hi . If possible, please explain why :

k^2 > 2k +1

I dont understand it . :confused:
 
  • #15
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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].
 
  • #16
2
0
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
 

Related Threads for: Induction Proof that 2^n > n^2 for n>=5

Replies
12
Views
2K
  • Last Post
Replies
5
Views
3K
Replies
5
Views
889
Replies
2
Views
713
Replies
17
Views
8K
Replies
4
Views
1K
  • Last Post
Replies
3
Views
4K
Top