How to find a closed form for a sum involving $\max(x,y)$

Question

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.

Answer 1

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

Answer 2

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.