Nested summation, change of variables

Question

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)$$

Answer 1

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.

Answer 2

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.

Answer 3

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}

Answer 4

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.