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!

Mathematical Induction where the base case starts above 1

  1. Aug 19, 2013 #1
    1. The problem statement, all variables and given/known data
    Find all natural numbers such that 2n ≥ (1+n)2, and prove your answer.

    2. The attempt at a solution
    I can see this is true for n=0 and n>5. I try to prove this using induction as follows
    20 =1≥ 1=(1+0)2
    base case: 26 =64≥ 49=(1+6)2 so it is true for n=6
    and suppose 2n ≥ (1+n)2 for all n≥6 then
    2n+2 =2n22 ≥4(1+n)2=4n2+8n+4≥n2+6n+9=(n+3)2

    I'm not sure if this correct because of the +2?
    Would I have do to it again with a base case of 7 to ensure every number is accounted for?
     
    Last edited: Aug 19, 2013
  2. jcsd
  3. Aug 19, 2013 #2
    I've actually just realised this can be done with n+1 and I'm just being silly. Sorry
     
  4. Aug 19, 2013 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, IF your "induction" step goes from n to n+2 you can prove the statement is true for all x greater than or equal to a by proving base cases n= a and n= a+1.

    But why are you using "n+2"? If [itex]2^n\ge (1+ n)^2[/itex] for all [itex]n\ge 6[/itex] then
    [itex]2^{n+1}= 2(2^n)\ge 2(1+ n)^2= 2(1+ 2n+ n^2)= 2+ 4n+ 2n^2= (4+ 4n+ n^2)+ (n^2- 2)[/itex]
    [itex]\ge ((n+1)+1)^2+ n^2- 2[/itex]
    and since [itex]n\ge 6[/itex], [itex]n^2- 2\ge 34[/itex] which is larger than 1.
     
  5. Aug 19, 2013 #4
    Clearly using n+2 was a mistake but I originally used it to see if this would result in an easier inequality for me to manipulate. I see your proof and it makes sense. I didnt see it originally but my original proof works for n+1 aswell.

    2n+1 =2n2 ≥2(1+n)2=2n2+4n+2≥n2+4n+4=(n+2)2

    But suppose I could not show this was true for n+1 does the logic for induction work if we use n+2. ie would the original proof using n+2 be sufficient although not elegant?
     
  6. Aug 19, 2013 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, I answered that before:
     
  7. Aug 19, 2013 #6
    Sorry I missed that but thanks for the clarification.
     
  8. Aug 19, 2013 #7

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A bit nitpicky, but if you're going to assume this then there's nothing left to prove
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Mathematical Induction where the base case starts above 1
  1. Where to start? (Replies: 1)

  2. Where to start? (Replies: 13)

  3. Mathematical induction (Replies: 8)

  4. Mathematical Induction (Replies: 11)

Loading...