1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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


    User Avatar
    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


    User Avatar
    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


    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted