How to find a closed form for a sum involving $\max(x,y)$ I have this sum:
$$\sum_{0\le y<k}\sum_{0\le x<k-y}k - \max(x,y)\ ,\qquad k\in\mathbb{N}$$
Is there a closed form for it? This is no homework, im just a highschool student whose math is too poor.
Another way to write the formula is:
$$\sum^{k-1}_{y=0}\sum^{k-y-1}_{x=0}(k-\max(x,y)),$$
If there is something unclear.
 A: I get that for $k$ even, the sum is $$\frac{1}{8}k(2k^2+3k+2),$$ and for $k$ odd, the sum is
$$\frac{1}{8}(k+1)(2k^2+k+1).$$
Maybe it is a good exercise to figure the sums yourself.
A: Hint: Split the sum into "sum of $k$" minus "sum of max".
Then draw the numbers to be added in a coordinate grid according to $x$ and $y$ values; I think you should consider even and odd values of $k$ separately.
For example, if $k=5$ you have to add the values
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

and from that subtract the sum of the values
4
3 3
2 2 2
1 1 2 3
0 1 2 3 4

Notice the mirror symmetry here:
4
3 3
2 2     2
1     1     2 3
    0     1 2 3 4

You have the numbers 0 + 1 + 2 on the diagonal $y=x$, and then there
are the numbers
4
3 3
2 2
1

which occur twice; moreover, 1+4=5 and 2+3=5, so they add up to three times 5
(times two).
Now try to generalize these observations to a general pattern. For odd $k$, say $k=2m+1$, I get the expression
$$
k^2 (k+1)/2 - (1+2k) m(m+1)/2.
$$
I'll leave the even case to you (or somebody else).  :)
