Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 30, 2008 #1
    1. The problem statement, all variables and given/known data
    Prove that [tex]2^{x} \geq x^{2}[/tex]
    [tex]\forall x\geq5[/tex]


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


    3. 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.
     
  2. jcsd
  3. Apr 30, 2008 #2
    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: Apr 30, 2008
  4. Apr 30, 2008 #3
    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.
     
  5. May 1, 2008 #4
    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.
     
  6. May 1, 2008 #5

    HallsofIvy

    User Avatar
    Science Advisor

    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?
     
  7. May 1, 2008 #6
    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]
     
  8. May 1, 2008 #7

    HallsofIvy

    User Avatar
    Science Advisor

    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: May 1, 2008
  9. May 1, 2008 #8
    :blushing::blushing::blushing:

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

    :blushing::blushing::blushing:
     
  10. Sep 26, 2008 #9
    what does RHS stand for? "added to factor the RHS"
     
  11. Sep 26, 2008 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    RHS=Right Hand Side (of the equation).
     
  12. Sep 26, 2008 #11
    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).
     
  13. Sep 27, 2008 #12

    HallsofIvy

    User Avatar
    Science Advisor

    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: Nov 15, 2011
  14. Sep 28, 2008 #13

    statdad

    User Avatar
    Homework Helper

    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]
     
  15. Nov 15, 2011 #14
    hi . If possible, please explain why :

    k^2 > 2k +1

    I dont understand it . :confused:
     
  16. Nov 15, 2011 #15

    HallsofIvy

    User Avatar
    Science Advisor

    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].
     
  17. Nov 15, 2011 #16
    thank you very much
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook