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?
 A: $$\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}$$
A: 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)$.
