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
    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 and can even be simplified to \sum_{0\le 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.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.