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