2
$\begingroup$

I have this sum:

$$\sum_{0\le y

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.

2 Answers 2

11

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

  • 0
    PS. You're going to need the well-known formula $1+2+\dots+k=k(k+1)/2$.2011-01-01
  • 0
    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$\max(x,y),$ as I don't know how to find a solution for this. – 2011-01-02
7

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.