Nested summation, change of variables My professor analyzed an algorithm using summations and I am very confused on how he simplified/created a closed form out of the summations. He said he used the change of variable method but he didn't explain how.
(i is a constant here):
$$\sum_{i=1}^{n} \sum_{j=i}^{n} j - i + 1$$ this was simplified to:
$$\sum_{i=1}^{n} \sum_{j=1}^{n - i + 1} j$$
I am confused as to how he rearranged the summation. He did another simplification that confused me:
$$\frac{1}{2}\sum_{i=1}^{n}(n - i + 1)(n - i + 2)$$ this was simplified to:
$$\frac{1}{2}\sum_{i=1}^{n} i(i + 1)$$
 A: Change of variables by linear substitution.   Remember the token is arbitrary; it can be alpha substituted for any token that is freely available, including linear functions of itself.   However, for clarity, we'll use the free token, $k$, for a bit.
$$\begin{align}&\qquad\sum_{i=1}^{n} \sum_{j=i}^{n} (j - i + 1) \\&=~\sum_{i=1}^{n} \sum_{k+i-1=i}^{n} (k+i-1 - i + 1) && \text{Substitute }j\gets (k+i-1)\\ &=~\sum_{i=1}^n\sum_{k=1}^{n-i+1} k\\ &=~\sum_{i=1}^{n} \sum_{j=1}^{n - i + 1} j && \text{Substitute }k\gets j\end{align}$$
That is it.
A: When in doubt, write it out.
$$\begin{align}
\sum_{i=1}^{n} \sum_{j=i}^{n} j - i + 1 & = \sum_{i=1}^{n}\left[(i-i+1)+(i+1-i+1)+\cdots+(n-i+1)\right]\\
&=\sum_{i=1}^{n}\left[1+2+3+\cdots+(n-i+1)\right]\\
&=\sum_{i=1}^{n} \sum_{j=1}^{n - i + 1} j
\end{align}$$
See if you can use this process to work out the second one as well.
A: In both variants it is one action which transforms the left-hand series into the right-hand series.

In the first example we shift the index $j$ of the inner sum by $i-1$ to start from $j=1$
\begin{align*}
\sum_{i=1}^n\sum_{j=i}^n(j-i+1)=\sum_{i=1}^{n}\sum_{j=1}^{n-i+1}j
\end{align*}
  
  
*
  
*In doing so the upper bound becomes $n-(i-1)$.
  
*To compensate this index change in the summand we replace each occurrence of $j$ by $j+(i-1)$ which simplifies the summand to $j$.
  

In the second example we do not shift the index, but change the order of summation.

We change the order of summation by substituting in the summand the index $i\rightarrow n-i+1$. This way the last summand becomes the first, the second last summand becomes the second, etc.
\begin{align*}
\frac{1}{2}\sum_{i=1}^n(n-i+1)(n-i+2)=\frac{1}{2}\sum_{i=1}^ni(i+1)
\end{align*}
  
  
*
  
*In order to do this index change we replace each occurrence of $i$ by $n-i+1$ resulting in the simpler right-hand sum.
  
*Lower bound and upper bound of the sum remain the same.

\begin{array}{l|l}
i&n-i+1\\
\hline\\
1&n\\
2&n-1\\
\vdots&\vdots\\
n&1
\end{array}
A: Substitute the limits of the inner sum in the summand and compare
$$j=i\to i-i+1=1,$$
$$j=n\to n-i+1.$$
The second case is similar, with order reversal.
