Double Summation $\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)=(2n+1)\sum_{r=1}^n r=3\sum_{r=1}^n r^2$

Question

It can be easily shown by step-by-step and rather messy summation over $j$ and then over $i$ that $$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)=\tfrac12 (2n+1)n(n+1)$$ Note that RHS is equivalent to $$\displaystyle (2n+1)\sum_{r=1}^n r$$

(1) Is there a clever transform that will simplify the original summation into the summation above without first working out the closed form?

It is interesting to note that RHS is also equivalent to $$3\sum_{r=1}^n r^2$$

(2) Is there also another clever transform to convert the original summation into this summation without first working out the closed form?

Answer 1

(1)

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

(2)

$$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)= \sum_{\begin{array} c 1 \le i \le n+1,\\ 0 \le j \le n-1, \\ 1 \le i+j \le n \end{array}} \!(i+j) + \!\!\sum_{\begin{array} c 1 \le i \le n+1,\\ 0 \le j \le n-1, \\ n+1 \le i+j \le 2n \end{array}} \!((i-1)+(j+1)) \\ =\sum_{k=1}^n\sum_{\begin{array} c 1 \le i \le n+1,\\ 0 \le j \le n-1, \\ i+j=k \end{array}} \!k + \!\sum_{\begin{array} c k=0 \\ (i-1=k) \end{array}}^n\!\!\sum_{\begin{array} c 0 \le j \le n-1, \\ n-k \le j \le 2n-1-k \end{array}} \!\!\!\!k + \!\sum_{\begin{array} c k=1 \\ (j+1=k) \end{array}}^n\!\sum_{\begin{array} c 1 \le i \le n+1, \\ n+2-k \le i \le 2n+1-k \end{array}} \!\!\!\!\!k \\ =\sum_{k=1}^n \,k \!\sum_{\begin{array} c 1 \le i \le k \\ (j=k-i) \end{array}} \!\!1 + \!\sum_{k=1}^n \,k \sum_{j=n-k}^{n-1} \!1 + \!\sum_{k=1}^n \,k\sum_{i=n+2-k}^{n+1} \!1 \\ = \sum_{k=1}^n k \cdot k + \sum_{k=1}^n k \cdot k + \sum_{k=1}^n k \cdot k = 3 \sum_{r=1}^n r^2$$

Answer 2

Let all summations have the upper bound $n$, it makes your life easier. Then expand layer by layer. I also pull out the last term in the first sum. $$\begin{align*}\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)&=\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j-1)+\sum_{j=1}^{n}(n+j)\\ &=\sum_{i=1}^{n}\left[\sum_{j=1}^{n}i+\sum_{j=1}^{n}j-n\right]+n^2+\sum_{j=1}^{n}j\\ &=\sum_{i=1}^{n}\sum_{j=1}^{n}i+\sum_{i=1}^{n}\sum_{j=1}^{n}j-n^2+n^2+\sum_{j=1}^{n}j\\ &=n\color{blue}{\sum_{i=1}^{n}i}+\underbrace{\sum_{i=1}^{n}}_{n}\color{blue}{ \sum_{j=1}^{n}j}+\color{blue}{\sum_{j=1}^{n}j}\\ &=\left(2n+1\right)\sum_{r=1}^{n}r \end{align*}$$ Note that terms in blue are identical. You can then factor $(2n+1)$ without knowing the right hand side.

To write this sum in $$3\sum_{r=1}^n r^2$$ is much more trickier, without realizing the fact that $$\sum_{r=1}^n r^2=\frac{n(n+1)(2n+1)}{6}.$$

Answer 3

Going over $i$ and then over $j$: $$ \begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &= \sum_{j=0}^{n-1}\sum_{i=1}^{n+1} (i+j) \\ &= \sum_{j=0}^{n-1} \frac{(n+1)(n+2)}{2} + (n+1) j \\ &= \frac{n(n+1)(n+2)}{2} + (n+1) \sum_{j=0}^{n-1} j \\ &= \frac{n(n+1)(n+2)}{2} + (n+1) \frac{(n-1)n}{2} \\ &= \frac{n(n+1)}{2} \left((n+2) + (n-1) \right) \\ &= \frac{n(n+1)(2n+1)}{2} \end{align} $$

Answer 4

In a patient, step-by-step manner, we have

$$\begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &=\sum_{i=0}^{n}\sum_{j=0}^{n-1}((i+1)+j)\\ &=\sum_{i=0}^{n}\sum_{j=0}^{n-1}(i+(1+j))\\ &=\sum_{i=0}^{n}\sum_{j=1}^{n}(i+j)\\ &=\sum_{i=0}^{n}\sum_{j=1}^ni+\sum_{i=0}^{n}\sum_{j=1}^nj\\ &=\sum_{i=0}^{n}\sum_{j=1}^ni+\sum_{j=1}^{n}\sum_{i=0}^nj\\ &=\sum_{i=0}^{n}ni+\sum_{j=1}^{n}(n+1)j\\ &=n\sum_{i=0}^ni+(n+1)\sum_{j=1}^nj\\ &=n\sum_{i=1}^ni+(n+1)\sum_{j=1}^nj\\ &=(2n+1)\sum_{r=1}^nr \end{align}$$

Answer 5

Part (1) $$\begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &=\sum_{r=1}^n\sum_{i=1}^r r+\sum_{r=n+1}^{2n}\sum_{i=r-n+1}^{n+1}r &&\scriptsize(r=i+j)\\ &=\sum_{r=1}^nr^2+\sum_{r=n+1}^{2n}r(2n+1-r)\tag{*}\\ &=\sum_{r=1}^n r^2+\sum_{r=1}^n(2n+1-r')r' &&\scriptsize(r'=2n+1-r)\\ &=\sum_{r=1}^n r^2+\sum_{r=1}^n r(2n+1-r) &&\scriptsize(r=r')\\ &=(2n+1)\sum_{r=1}^n r\qquad\blacksquare\end{align}$$

Part (2)

Note that $$\begin{align} \sum_{r=n+1}^{2n}r\ (2n+1-r) &=\sum_{r=n+1}^{2n}\bigg[\big(2n+1-r\big)+\big(2r-2n-1\big)\bigg]\big(2n+1-r\big)\\ &=\sum_{r'=1}^n\bigg[r'+\big(2n-2r'+1\big)\bigg]\; r' &&\scriptsize (r'=2n+1-r)\\ &=\sum_{r=1}^n r^2+\sum_{r=1}^n r\; \big(2n-2r+1\big) &&\scriptsize (r=r')\\ &=\sum_{r=1}^n r^2+\sum_{t=1}^n (n+1-t)\ (2t-1) &&\scriptsize (t=n+1-r)\\ &=\sum_{r=1}^n r^2+\sum_{t=1}^n\sum_{s=t}^n (2t-1)\\ &=\sum_{r=1}^n r^2+\sum_{s=1}^n\sum_{t=1}^s (2t-1)\\ &=\sum_{r=1}^n r^2+\sum_{s=1}^n s^2\\ &=2\sum_{r=1}^n r^2 \end{align}$$ From $(*)$ in Part (1) above, $$\begin{align} \sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j) &=\sum_{r=1}^n r^2+\sum_{r=n+1}^{2n}r\ (2n+1-r)\\ &=\sum_{r=1}^n r^2+2\sum_{r=1}^n r^2\\ &=3\sum_{r=1}^n r^2\qquad\blacksquare\end{align}$$

A tabulated example for $n=5$ is shown below.

Answer 6

Denoting: $\sum_{k=1}^n1=A$: $$\sum_{i=1}^{n+1}\sum_{j=0}^{n-1}(i+j)=\sum_{i=1}^{n+1}(in+(A-n))=\sum_{i=1}^{n+1}(A+n(i-1))=\\ A(n+1)+n\sum_{i=1}^{n+1}(i-1)=A(n+1)+nA=(2n+1)A=\tfrac12 (2n+1)n(n+1).$$