Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 11 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.