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!

Discrete Math Proof n^2 > n +1

  1. Aug 5, 2012 #1
    1. The problem statement, all variables and given/known data
    For any given n, where n is an element of the natural number set, prove n^2 > n +1, for all n > 1.

    2. Relevant equations
    This week in lecture we defined the greater than relationship as:

    Let S = Natural numbers
    Let R = {(a,b): [itex]\exists[/itex] c: a = b+c}
    then aRb



    3. The attempt at a solution

    My first thought was show a general expression of either an odd of even number (n = 2x + 1 or n = 2x), but the resultant (4x^2 + 4x +1 > 2x + 2 and 4x^2 > 2x +1 for odd/even respectively) doesn't really give me anything useful as far as I can see.

    I can see that it would be true, as n = 2 would be 4 > 3, and n= 3 would be 9 > 4, I'm just not sure on how to get started.

    Some literature on approaches to getting started on proofs would be great, as I find I'm fairly hit/miss. I can either see the approach or I stand there going "I know it's true, but I can't show it's true".
     
    Last edited: Aug 5, 2012
  2. jcsd
  3. Aug 5, 2012 #2

    MathematicalPhysicist

    User Avatar
    Gold Member

    Here's one approach.

    n^2-n = n(n-1)

    n>1 thus (n-1)>=1, now n(n-1)>= n >1
     
  4. Aug 5, 2012 #3
    Sorry, still not sure how having the form,

    n(n-1) > 1 for all n > 1,

    helps me in this?
     
  5. Aug 5, 2012 #4
    One way to do it would be to rewrite it as n^2 - n -1 > 0, and show that that is true for n > 1
     
  6. Aug 5, 2012 #5
    Hmm.. explain it to me like I'm 5. I last did math proof type subjects in '99, prior to this my degree has had calculus and stats which I had no issue with.
     
  7. Aug 5, 2012 #6

    ehild

    User Avatar
    Homework Helper
    Gold Member

    See the previous post #2. The original inequality can be written as n2-n>1, as you can subtract the same amount from both sides of an inequality: for example, if a>b, a-1>b-1.

    n2-n=n(n-1). So you have to prove that n(n-1)>1 if n>1 integer.
    If n>1 n-1≥1. You multiply n with a number greater then 1. Will the result greater or less than n?

    ehild
     
  8. Aug 5, 2012 #7
    Alright, that makes sense. Issue is I'm not sure if this is the sort of proof I'm meant to be doing for it.

    I think I'll go bang my head on a book.

    Thanks.
     
  9. Aug 5, 2012 #8

    ehild

    User Avatar
    Homework Helper
    Gold Member

    It is a proof and simple enough. If you want to apply the definition find that "c" >0 that makes (n+1)+c=n2. It is just the difference n2-(n+1), isn't it? You need to prove that n2-n-1>0.

    ehild

    EDITED!
     
    Last edited: Aug 5, 2012
  10. Aug 5, 2012 #9

    MathematicalPhysicist

    User Avatar
    Gold Member

    ehild, you meant n^2-n-1>0 not n^2-n+1.

    You can do this also by induction, though it's really easy without.
     
  11. Aug 5, 2012 #10

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Thank you, I corrected it.

    ehild
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete Math Proof n^2 > n +1
Loading...