Results 1 to 7 of 7

Math Help - Help with a proof

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    43
    Thanks
    5

    Talking Help with a proof

    Ok I've just started a university maths course and the first thing we are learning is proofs. (I hope this is the right sub-forum )
    I get the concept and all but I am reading a book on the subject anyway and it has a proof early on that I don't quite get the reasoning of.
    Its to prove 2^n > n^2 for n>or=5.

    I get that we have to prove that 2^(n+1) > (n+1)^2

    So we multiply 2^n > n^2 X2
    2X 2^n = 2^(n+1) > 2X n^2 = 2n^2 = n^2 + n^2 = n^2 +nn

    Now this is the part that I don't quite understand. It has;

    Since n> or =5, we have n> or =3 (Why 3? In using 3 there is an inequality in the wrong direction?) so

    nn> or = 3n = 2n+n > or = 2n+1 (I don't see how you can just assume that the n can turn into a 1 either)

    I see that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2
    but can't justify why you can just use the things pointed out above to get the reasoning.

    Personally I would have argued (this is by no means a correct statement so if I'm gravely wrong please say) That n^2 + n^2 is always going to be greater than n^2 + 2n + 1 for n> or =5 as n^2 is always going to be larger then 2n + 1 for numbers that high. I know thats not quite induction but to me it makes more sense the swapping out n for convenient numbers.

    Thanks for the help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Quote Originally Posted by rushton View Post
    Ok I've just started a university maths course and the first thing we are learning is proofs. (I hope this is the right sub-forum )
    I get the concept and all but I am reading a book on the subject anyway and it has a proof early on that I don't quite get the reasoning of.
    Its to prove 2^n > n^2 for n>or=5.

    I get that we have to prove that 2^(n+1) > (n+1)^2

    So we multiply 2^n > n^2 X2
    2X 2^n = 2^(n+1) > 2X n^2 = 2n^2 = n^2 + n^2 = n^2 +nn

    Now this is the part that I don't quite understand. It has;

    Since n> or =5, we have n> or =3 (Why 3? In using 3 there is an inequality in the wrong direction?) so

    nn> or = 3n = 2n+n > or = 2n+1 (I don't see how you can just assume that the n can turn into a 1 either)

    I see that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2
    but can't justify why you can just use the things pointed out above to get the reasoning.

    Personally I would have argued (this is by no means a correct statement so if I'm gravely wrong please say) That n^2 + n^2 is always going to be greater than n^2 + 2n + 1 for n> or =5 as n^2 is always going to be larger then 2n + 1 for numbers that high. I know thats not quite induction but to me it makes more sense the swapping out n for convenient numbers.

    Thanks for the help!
    Hi rushton,

    Since it is given that, n>5\Rightarrow{n>3}

    Since n is a positive integer, we can multiply both sides of the inequality by n,

    n^2>3n\Rightarrow{n^2>2n+n}

    n>1\Rightarrow{n^2>2n+n>2n+1}

    We are using 3n particularly because we know that we have to make (n+1)^2 in the right hand side of the inequality.
    Last edited by Sudharaka; February 20th 2011 at 03:53 AM. Reason: Error shown by emakarov
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2011
    Posts
    43
    Thanks
    5
    So just because we know n> or =5 we can use n>3 and n>1 as n is larger then 1,2,3 or 4. Which, I'm assuming, this means in proofs we can change variables around to get answers we need as long as the change fits into the given criteria. (For an example if we had a proof xn>yn to do where n>3 we could not change an n in the right hand side to a 4 but we could change it to a 1,2 or a 3)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Quote Originally Posted by rushton View Post
    So just because we know n> or =5 we can use n>3 and n>1 as n is larger then 1,2,3 or 4.
    Yes because, we know that, n>5~and~5>4. Therefore, n>4 Hope you understood.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Quote Originally Posted by rushton
    Since n> or =5, we have n> or =3 (Why 3? In using 3 there is an inequality in the wrong direction?)
    I agree with the reply above:
    We are using 3n particularly because we know that we have to make (n+1)^2 in the right hand side of the inequality.
    But the short answer to "Why 3?" questions is, because it is true (namely, if n >= 5, then n >= 3). It is one thing to find that some step in a proof is incorrect and another to not understand the author's intention behind a step. The former obviously invalidates the whole proof; the latter happens all the time and is normal. Hopefully, when you reach the end of the proof, you will understand why 3 and not 2 or 4 is chosen. In fact, you write that you see "that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2".

    Similarly, if n >= 5, then n > 1, so 2n + n > 2n + 1. To be extremely formal, you start with a true inequality n > 1 (which follows from n >= 5) and add 2n to both sides.

    Personally I would have argued (this is by no means a correct statement so if I'm gravely wrong please say) That n^2 + n^2 is always going to be greater than n^2 + 2n + 1 for n> or =5 as n^2 is always going to be larger then 2n + 1 for numbers that high.
    This is precisely how the proof proceeds, it just justifies n^2 > 2n + 1 in more detail.

    Quote Originally Posted by Sudharaka
    Since n is a positive integer, we can multiply both sides of the inequality by n,

    n^2>3nn^2>2n+n
    You probably mean n^2>3n=2n+n.
    Quote Originally Posted by Sudharaka
    n>1\Rightarrow n^2>2n+n>2n+1
    I would write, Since n > 1 and, as we have shown, n^2>2n+n, we have n^2 > 2n + 1. (The fact that n>1 does not imply that n^2>2n+n.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2011
    Posts
    43
    Thanks
    5
    Thank you very much both of you!
    I totally understand how it is done now and understand proofs and induction more in turn.
    I'm doing this degree externally so I can see that this forum is going to a lot of help.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Quote Originally Posted by emakarov View Post
    I agree with the reply above:But the short answer to "Why 3?" questions is, because it is true (namely, if n >= 5, then n >= 3). It is one thing to find that some step in a proof is incorrect and another to not understand the author's intention behind a step. The former obviously invalidates the whole proof; the latter happens all the time and is normal. Hopefully, when you reach the end of the proof, you will understand why 3 and not 2 or 4 is chosen. In fact, you write that you see "that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2".

    Similarly, if n >= 5, then n > 1, so 2n + n > 2n + 1. To be extremely formal, you start with a true inequality n > 1 (which follows from n >= 5) and add 2n to both sides.

    This is precisely how the proof proceeds, it just justifies n^2 > 2n + 1 in more detail.

    You probably mean n^2>3n=2n+n.
    I would write, Since n > 1 and, as we have shown, n^2>2n+n, we have n^2 > 2n + 1. (The fact that n>1 does not imply that n^2>2n+n.)
    Dear emakarov,

    Thanks for pointing out those mistakes. I think I need to improve my way of expressing ideas. Most of the time I myself is not satisfied when I read a reply I had already posted.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 12:13 PM
  2. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum