Need help understanding partial solution for sum $\sum_{1\leq i \leq j \leq n}(j-i)$ Let's consider the following sum:
$$\sum_{1\leq i \leq j \leq n}(j-i)$$
Here are some progressions from my Discrete Math lecture:
$$\sum_{1\leq i \leq j \leq n}(j-i)=\sum_{i=1}^n\sum_{k=0}^{n-i}k=\sum_{i=1}^n(n-i)(n-i+1)/2=\sum_{l=0}^{n-1}l(l+1)/2$$
I don't understand what happened there at all. Could anyone explain it to me? I would be also thankful for directing me to some material connected with solving the sums this way (as in my lecture this solution is basically pulled out of a hat and I don't see how could I come up with that).
 A: The first step is rewriting the single two-index sum as a double sum, separating the indices. The original sum is taken over all pairs of integers $i$ and $j$ between $1$ and $n$ (inclusive) with $i\le j$. Instead of thinking of them all at once, let’s sort them according to $i$. Clearly $i$ can be anything from $1$ through $n$. Once we’ve chosen an $i$, however, $j$ must be at least that big: the original complicated summation has no term like $2-3$, with $i=3$ and $j=2$. Thus, $j$ must run from $i$ up through $n$, and we have
$$\sum_{1\le i\le j\le n}(j-i)=\sum_{k=1}^n\sum_{j=i}^n(j-i)\;.$$
As $j$ runs from $i$ up to $n$, $j-i$ runs from $i-i=0$ up to $n-i$, so if we let $k=j-i$, we can rewrite this as
$$\sum_{i=1}^n\sum_{k=0}^{n-i}k\;.$$
Now recall that $\sum_{k=0}^mk=\sum_{k=1}^mk=\frac12m(m+1)$, and apply this to the inner summation with $m=n-i$:
$$\sum_{k=0}^{n-i}k=\frac12(n-i)(n-i+1)\;,$$
so
$$\sum_{i=1}^n\sum_{k=0}^{n-i}k=\sum_{i=1}^n\frac12(n-i)(n-i+1)\;.$$
Now let $\ell=n-i$: clearly $(n-i)(n-i+1)=\ell(\ell+1)$, but what about the index? When $i=1$, $n-i=n-1$, and as $i$ increases to $n$, $n-i$ decreases nown to $n-n=0$. Thus, as $i$ runs from $1$ up through $n$, $\ell$ runs from $n-1$ down through $0$. It makes no difference in what order we add these $n$ terms, so we might as well let $\ell$ run from $0$ up through $n-1$ instead, getting
$$\sum_{\ell=0}^{n-1}\frac12\ell(\ell+1)\;.$$
The treatment of summation in Chapter $2$ of Graham, Knuth, & Patashnik, Concrete Mathematics, is quite extensive and very readable.
A: First equality: It was defined $k=j-i$ and therefore the Summation over the new variable $k$ goes from $i-i=0$ to $n-i$; Summation over $i$ remains the same. The double sum $\sum_{1 \leq i \leq j \leq n}$ can be expressed as: $\sum_{1 \leq i \leq j \leq n} (j-i) = \sum_{i=1}^n \sum_{k=0}^{n-i} k$.
Second equality: The identity $\sum_{k=0}^m k = \frac{m(m+1)}{2}$ for arbitrary numbers $m$ was used.
Third equality: Also Evaluation of sums, see here at "Identities".
