# Help with this double summation

I'm having trouble when the indexes are related in a double summation. For example, this problem: $\sum^n_{i = 1} \sum^n_{j = i+1} j - i + 2$

How could I sum this and what's a general approach to this type of double/triple summations?

• You have to be very careful with what the limits are, and how you're summing them up. Draw a picture showing you the region that you're interested in, which makes it easier to understand the new limits to use. May 26 '13 at 0:04
• I think attempting to draw the region will only make things more complicated. Just break up the sums and shift the indexes of each sum up and down accordingly. May 26 '13 at 0:13

$$\sum^n_{i = 1} \sum^n_{j = i+1} j - i + 2= \sum^n_{i = 1} \sum^{n-i}_{j =1} j + 2=\sum^n_{i = 1}\frac{(n-i)^2+(n-i)}{2}+2(n-i)$$ $$=\sum_{i=1}^{n-1}\frac{i^2+i}{2}+2i=\sum_{i=1}^{n-1}\frac{i^2+5i}{2}=\frac{1}{2}\sum_{i=1}^{n-1}i^2+\frac{5}{2}\sum_{i=1}^{n-1}i=\frac{n(n-1)(n+7)}{6}$$

It depends greatly on what you know. I might be inclined to let $k=j-i$ and evaluate it like this:

\begin{align*} \sum_{i=1}^n\sum_{j=i+1}^n(j-i+2)&=\sum_{i=1}^n\sum_{k=1}^{n-i}(k+2)\\\\ &=\sum_{i=1}^n\left(\sum_{k=1}^{n-i}k+2(n-i)\right)\\\\ &=\sum_{i=1}^n\frac12(n-i)(n-i+1)+2\sum_{i=1}^n(n-i)\\\\ &=\sum_{i=1}^n\left(\binom{n-i+1}2+2(n-i)\right)\\\ &=\sum_{i=0}^{n-1}\left(\binom{i+1}2+2i\right)\\\\ &=\binom{n+1}3+2\binom{n}2\\\\ &=\binom{n}3+3\binom{n}2\;. \end{align*}

Of course, you need to know some binomial coefficient identities in order to do that.

Or you could go at it straight up. First,

$$\sum_{i=1}^n\sum_{j=i+1}^n(j-i+2)=\sum_{i=1}^n\left(\sum_{j=i+1}^nj-\sum_{j=i+1}^n(i-2)\right)\;.$$

Now $\sum_{j=i+1}^nj$ is just the sum of an arithmetic progression, so it’s $\frac12(n+i+1)$. And $\sum_{j=i+1}^n(i-2)=(n-i)(i-2)$, since it’s the sum of $n-i$ identical terms. The double sum then reduces to a single sum over $i$ of a quadratic in $i$, which is straightfoward to evaluate if you know that $\sum_{i=1}^ni^2=\frac16n(n+1)(2n+1)$.