Results 1 to 4 of 4

Math Help - Help with last step of proof

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    62

    Help with last step of proof

    I'm stuck on the last step of proof involving the sum of divisors function. I need to show that 1+2+3+...+n <= n^2.

    <= - is less than or equal to

    It's probably an obvious step, but I can't seem to see it right now.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2
    It is (well-)known that 1 + 2 + 3 + ... + n = n(n + 1)/2.
    Since (n + 1)/2 = n/2 + 1/2 <= n for n = 1, 2, 3, ....
    We can replace (n + 1)/2 in the above equality with (just) "n", and change to inequality.


    If you don't "know" the result, it's a common elementary proof by mathematical induction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,337
    Thanks
    1247
    Quote Originally Posted by TheChaz View Post
    It is (well-)known that 1 + 2 + 3 + ... + n = n(n + 1)/2.
    Since (n + 1)/2 = n/2 + 1/2 <= n for n = 1, 2, 3, ....
    We can replace (n + 1)/2 in the above equality with (just) "n", and change to inequality.


    If you don't "know" the result, it's a common elementary proof by mathematical induction.
    No need for induction. You can write the sum S as

    S = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n

    or

    S = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1.

    Adding the corresponding terms in the two series gives

    S + S = (n + 1) + (n - 1 + 2) + (n - 2 + 3) + ... + (3 + n - 2) + (2 + n - 1) + (1 + n)

    2S = (n + 1) + (n + 1) + (n + 1) + ... + (n + 1) + (n + 1) + (n + 1) [n times]

    2S = n(n + 1)

    S = n(n + 1)/2
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by JSB1917 View Post
    I'm stuck on the last step of proof involving the sum of divisors function. I need to show that 1+2+3+...+n <= n^2.

    <= - is less than or equal to

    It's probably an obvious step, but I can't seem to see it right now.
    That is consequence of the fact that is...



    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: October 15th 2011, 12:26 PM
  2. Proving step to full proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 3rd 2010, 11:12 PM
  3. Help with the final step of a proof (valid argument)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2010, 10:12 PM
  4. Radon Nikodym computation, step of a proof
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 5th 2010, 10:09 AM
  5. Step function proof
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: May 10th 2009, 12:58 PM

Search Tags


/mathhelpforum @mathhelpforum