1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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
    Staff Emeritus
    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: 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
    Staff Emeritus
    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: 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
    Staff Emeritus
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction Proof that 2^n > n^2 for n>=5
Loading...