Triangular Summation $\displaystyle\sum_{i=0}^n\sum_{j=0}^i (i+j)=3\sum_{i=0}^n\sum_{j=0}^i j$

Question

It can be easily shown that the summation $$\sum_{i=0}^n \sum_{j=0}^i (i+j)\tag{*}$$ is equivalent to $$\frac 12 n(n+1)(n+2)$$ which can also be written as $$3\binom {n+2}3$$

This is the same result as the summation $$3\sum_{i=0}^n\sum_{j=0}^ij\tag{**}$$

Is it possible to transform summation $(*)$ to summation $(**)$ directly without first working out the closed form?

Answer 1

Another way maybe more beautiful than my previous answer:

\begin{align*}\sum_{i=0}^n \sum_{j=0}^i (i+j)&=\sum_{i=0}^n \sum_{j=0}^i ((i-j)+j+j)\\&= \sum_{i=0}^n \left[\left(\sum_{j=0}^i (i-j)\right)+2\left(\sum_{j=0}^i j\right)\right]\\&=3\sum_{i=0}^n\sum_{j=0}^ij\end{align*}

Where $\sum_{j=0}^i (i-j)=\sum_{j=0}^i j$ by change of indices $j'=i-j$.

Answer 2

\begin{align*} \sum_{i=0}^n\sum_{j=0}^i(i+i)&= \sum_{i=0}^n\left[\sum_{j=0}^i i+\sum_{j=0}^i j\right]\\ &=\sum_{i=0}^n\left[i\sum_{j=0}^i 1+\sum_{j=0}^i j\right]\\ &=\sum_{i=0}^n\left[i(i+1)+\sum_{j=0}^i j\right]\\ &=\sum_{i=0}^n\left[2\sum_{j=0}^i j+\sum_{j=0}^i j\right]\\ &=\sum_{i=0}^n3\sum_{j=0}^i j\\ &=3\sum_{i=0}^n\sum_{j=0}^i j. \end{align*}

Answer 3

$$\sum_{i=0}^n \sum_{j=0}^i (i+j)=\sum_{i=0}^n\left(\sum_{j=0}^i i+\sum_{j=0}^ij\right)=\sum_{i=0}^n\left(i(i+1)+\sum_{j=0}^ij\right)=\color{blue}{\sum_{i=0}^ni(i+1)}+\sum_{i=0}^n\sum_{j=0}^ij$$ We have one term now. Note that

$$\sum_{i=0}^n\dfrac{i(i+1)}{2}=\dfrac{\sum_{i=0}^ni(i+1)}{2}=\sum_{i=0}^n\left(\sum_{j=0}^ij\right)$$ Then $$\sum_{i=0}^ni(i+1)=\color{blue}{2\sum_{i=0}^n\left(\sum_{j=0}^ij\right)}.$$

Answer 4

Let $k=i+j$. \begin{equation} \sum_{i=0}^n\sum_{j=0}^i (i+j) = \sum_{i=0}^n\sum_{k=i}^{2i}k \end{equation} Hence it is sufficient to show \begin{equation} \sum_{i=0}^n\sum_{k=i}^{2i}k = \sum_{i=0}^n\sum_{j=0}^i 3j \end{equation} Or simply \begin{equation} \sum_{k=i}^{2i} k = \sum_{j=0}^i 3j \end{equation} Induction on i: \begin{equation} \sum_{k=i+1}^{2i+2} k = \sum_{k=i}^{2i} k + 3(i+1) = \sum_{j=0}^i 3j +3(i+1) = \sum_{j=0}^{i+1} 3j \end{equation} and base step is easy.