# Thread: Help with last step of proof

1. ## 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.

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.

3. Originally Posted by TheChaz
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

4. Originally Posted by JSB1917
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

$\displaystyle \chi$ $\displaystyle \sigma$