# 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. – Calvin Lin 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. – Ethan 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)$.