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!

Proof by induction

  1. Nov 15, 2008 #1
    1. The problem statement, all variables and given/known data
    Prove that ([tex]\forall[/tex]n in the set of Natural numbers )[(n [tex]\geq[/tex] 9) [tex]\Rightarrow[/tex] (2n > 4n2 + 1)]


    2. Relevant equations
    To do proof by induction you must first prove for n = 1, then assume true for n and then show for n+1


    3. The attempt at a solution
    So for n=1 i have RHS:29 = 512 and 4.92 + 1 = 325
    So (2n > 4n2 + 1)] for n=1

    Now assume true for n

    Show for n+1: (2n+1 > 4(n+1)2 + 1)]
    So 2 n+1can also be written as 2 n . 21
    Thus 2 n+1> 4(n+1) 2 + 1)] = 2n . 21 > [4(n+1)2 + 1].2
    which is the same as 2n . 21 > 8(n+1)2 + 2

    And now i'm stuck as to how to arrange this to give me the right answer
     
    Last edited: Nov 15, 2008
  2. jcsd
  3. Nov 15, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No. That "thus" is what you are trying to prove!
    What you KNOW is that 2n+1= 2n(2)> (4n2+ 1)(2)= 8n2+ 2
    Now, can you prove that that is larger than 4(n+1)2+ 1= 4n2+ 8n+ 5? 8n2+ 2> 4n2+ 8n+ 5, if and only if 4n2- 8n- 4>> 0 which is the same as n2- 2n- 1> 0. For what values of n is that true?

     
    Last edited: Nov 15, 2008
  4. Nov 15, 2008 #3
    Is that last bit right? Because I multiplied it out to be 8n2 + 16n + 10?
     
  5. Nov 15, 2008 #4
    Hang on, no I think i see what you were doing now....I'll just have a go :)
     
  6. Nov 15, 2008 #5
    But still.... are you just rearranging this because if so how does it change to >> and why is it -4 and not -3?
     
  7. Nov 15, 2008 #6
    Okay so disregarding my previous questions for the time being, In answer to your question about for which n values does it hold true, I did it like this:

    n2- 2n- 1> 0.
    (n-1)2 - 2 > 0
    (n-1)2 > 2
    (n-1) > 4
    n > 5

    So for values greater than 5?
     
  8. Nov 15, 2008 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes. And since your original problem specified "[itex]n\ge 9", ...
     
  9. Nov 15, 2008 #8
    But i don't understand how you rearranged an equation to get n2 - 2n- 1 and then once i've found which values of n this equation holds true for, how does this show 2 n+1 > 4(n+1)2 + 1?
     
  10. Nov 16, 2008 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I wrote before:
    What you KNOW is that 2n+1= 2n(2)> (4n2+ 1)(2)= 8n2+ 2
    Now, can you prove that that is larger than 4(n+1)2+ 1= 4n2+ 8n+ 5?
    4(n+1)2+ 1= 4(n2+ 2n+ 1)+ 1= 4n2+ 8n+ 5 and you to show that is smaller than 8n2+ 2. In other words, you want 8n2+ 2> n2+ 8n + 5 which reduces to (8- 4)n2- 8n+ (2- 5)= 4n2- 8n -3> 0. You are right. I accidently had "- 4" instead of -3 before.

    It is simplest to look at the equation 4n2- 8n- 3= 0: 4n2- 8n+ 4= 3+ 4= 7 or 4(n2- 2n+1)= 4(n-1)2= 7. Solving that gives [itex]n= 1+ \sqrt{7}/2. as the only positive value of n at which the original inequality can change from "<" to ">" That is approximately 2.3. Taking n= 2 gives 4n2- 8n -3= 16- 16- 3= -3 which is negative. Taking n= 3 gives 4n2- 8n -3= 36- 24- 3= 9 which is positive. 4n2- 8n -3> 0 is true for all n greater than 2.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...