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 wish to calculate $\sum_{x=1}^{n}\sum_{y=1}^{n} f(x,y)$ where $x>2y$. I can do this by changing $y$'s upperbound to the floor of $(x-1)/2$ but this makes simplification of the summation harder later. Is there a way using inclusion-exclusion to simplify this sum?

share|improve this question
    
What is $f(x,y)$ ? A polynomial ? –  Dietrich Burde Dec 18 '13 at 21:20

2 Answers 2

up vote 1 down vote accepted

No need to evaluate a floor. Since $x > 2y$, $x \geq 2y + 1:$

$$\sum_{y=1}^n \sum_{x=2y+1}^n f(x,y).$$

share|improve this answer

According to my own experience, for the purpose of simplifying a double sum, the first and most tricky and powerful step is to suitably extend the defining domain of $f(x,y)$ so that we have $$\sum_{x=1}^n\sum_{y=1}^nf(x,y) =\sum_{x=-\infty}^{+\infty}\sum_{y=-\infty}^{+\infty}f(x,y),$$ which is usually written in the notation $$\sum_{x}\sum_{y}f(x,y),$$ for the sake of emphasizing that we now have a summation of "standard" form in hand. In other words, we simply define $f(x,y)=0$ when $x<1$ or $x>n$ or $y<1$ or $y>n$. For this problem, we can define $f(x,y)=0$ for $x\le 2y$. The remaining work is routine, just to simply $\sum_{x}\sum_{y}f(x,y)$ by using standard transformations and known formulas. For example, instead of writing $$\sum_{k=0}^n{n\choose k}=2^n,$$ I prefer the "standard" form $$\sum_{k}{n\choose k}=2^n.$$ This trick sometimes brings great convenience, and maybe helpful to your specific problem.

share|improve this answer

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.