Evaluating double sums with related indices

Question

I am having trouble finding any techniques that allow people to solve double sums where the indices rely on each other. For example, suppose I have the following sum:

$$\sum_{i=1}^{n-1}\sum_{j=i+1}^n i + j$$

What techniques can I use to eliminate the sums, and arrive at a simple algebraic expression in terms of only n?

Answer 1

We obtain \begin{align*} \color{blue}{\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(i+j)}&=\sum_{1\leq i<j\leq n}(i+j)\tag{1}\\ &=\sum_{j=2}^n\sum_{i=1}^{j-1}(i+j)\tag{2}\\ &=\sum_{j=2}^n\left(\sum_{i=1}^{j-1}i+(j-1)j\right)\tag{3}\\ &=\sum_{j=2}^n\left(\frac{1}{2}(j-1)j+(j-1)j\right)\tag{4}\\ &=\frac{3}{2}\sum_{j=1}^n(j-1)j\tag{5}\\ &=\frac{3}{2}\left(\frac{1}{6}n(n+1)(2n+1)-\frac{1}{2}n(n+1)\right)\tag{6}\\ &\,\,\color{blue}{=\frac{1}{2}(n-1)n(n+1)}\tag{7} \end{align*}

Comment:

• In (1) we write the index region somewhat more conveniently.

  Note that we assume the index $j$ is a bound variable and so we write $(i+j)$ consequently in parenthesis.

• In (2) we exchange the sums so that the inner sum starts now with $i=1$.

• In (3) we use the summation formula $\sum_{k=1}^n c= n\cdot c$.

• In (4) we use the summation formula $\sum_{k=1}^n k=\frac{1}{2}n(n+1)$.

• In (5) we do some simplifications and start with $j=1$ without changing anything since we are adding $0$ only.

• In (6) we use the formula $\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)$ and the same as in (4).

• In (7) we do some final simplifications.

Answer 2

We can sum at first the inner summation that is

$$\sum_{j=i+1}^n i + j=i\sum_{j=i+1}^n 1 +\sum_{j=i+1}^n j=i(n-i)+\frac{n(n-1)}{2}-\frac{i(i+1)}{2}$$

and then

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

$$=\frac{n(n-1)}{2}\sum_{i=1}^{n-1}1+\sum_{i=1}^{n-1}\left(-\frac32i^2+i\left(n-\frac12\right)\right)$$