How can I solve this summation?

I've been trying to solve this problem for quite some time now and I can't think of how to reduce the inner summation to a smaller problem. Usually when I have variables in the upper and lower bound of the summation, I just do

$$(upper bound - lower bound + 1) * a$$ where $a$ is the value inside the summation. But this wont work here because I'll still have the $j$ variable inside the outer sigma. Is there an easier way to do this that I don't know?

$$\sum_{i=0}^{n}\,\,\sum_{j = i} ^ {n-1}(j -i +1 )$$

According to WolframAlpha, the solution should be:

$$\frac 16 n(n^2 + 3n + 2)$$

Answer

This method doesn't use combinatorics explicitly, but reduces the sum to more well-known ones.

The terms $-i$ and $1$ don't depend on the inner summation variable $j$, so you can take them out using the method you describe:

$$\begin{align}\sum_{i=0}^n \sum_{j=i}^{n-1} (j - i + 1) &= \sum_{i=0}^n \left( (n - i)(1-i) + \sum_{j=i}^{n-1}j\right)\end{align}$$

Also, we evaluate the inner summation as $T(n-1) - T(i-1)$ where $T(x)$ is the $x$th triangular number, and $T(-1)=T(0)=0$

$$\begin{align}\sum_{i=0}^n \sum_{j=i}^{n-1} (j - i + 1) &= \sum_{i=0}^n \left( (n - i)(1-i) + \sum_{j=i}^{n-1}j\right) \\
&= \sum_{i=0}^n \left( n - i(n+1) + i^2 + \sum_{j=i}^{n-1}j\right) \\
&= n \sum_{i=0}^n 1 - (n+1) \sum_{i=0}^n i + \sum_{i=0}^n i^2 + \sum_{i=0}^n \sum_{j=i}^{n-1}j \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + \sum_{i=0}^n \sum_{j=i}^{n-1}j \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + \sum_{i=0}^n (T(n-1) - T(i-1)) \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + (n+1)T(n-1) - \sum_{i=0}^n T(i-1) \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + (n+1)T(n-1) - \sum_{i=1}^{n-1} T(i) \\
&= (n+1) \underbrace{\left( n - (T(n) - T(n-1)) \right)}_0 + \sum_{i=0}^n i^2 - \sum_{i=1}^{n-1} T(i) \\
&= \sum_{i=0}^n i^2 - \sum_{i=1}^{n-1} T(i) \\
\end{align}$$

Now the summation is expressed in terms of more standard summations whose values are well known.

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

And we can evaluate:

$$\begin{align}\sum_{i=0}^n i^2 - \sum_{i=1}^{n-1} T(i) &= \frac 1 6 n (n+1) \left( (2n+1) - (n-1)\right)\\
&= \frac 1 6 n (n+1) (n+2)\\

&= \frac 1 6 n (n^2 + 3n + 2)\\
\end{align}$$