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

-

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

-
PS. You're going to need the well-known formula $1+2+\dots+k=k(k+1)/2$. – Hans Lundmark Jan 1 '11 at 16:24
Thank you very much. After some thinking before going to sleep, I found out that I derived the wrong formula out of thee problem, so it's $\sum_{0\le y<k}\sum_{0\le x<k-y}k - 1 - x - y$ and can even be simplified to $\sum_{0\le y<k}\sum_{0\le x<k-y}y$ with some thinking about the problem. I was just afraid of the $\max(x,y),$ as I don't know how to find a solution for this. – FUZxxl Jan 2 '11 at 2:38

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.

-