Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Evaluate
$$\sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^n \frac {i(j+2)(k+4)}{15} $$
Background
Many basic summation questions on MSE relate to a single index - it might be interesting to devise a question where the summand is a product of the three indices but can be solved easily.
$$\begin{align} \sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^n\frac{i(j+2)(k+4)}{15} &=\sum_{k=1}^n\sum_{j=1}^k\sum_{i=1}^j \frac{i(j+2)(k+4)}{15} &&(1\le i\le j\le k\le n)\\ &=\frac 1{15}\sum_{k=1}^n(k+4)\sum_{j=1}^k(j+2)\sum_{i=1}^j i\\ &=\sum_{k=1}^n\frac {k+4}5\sum_{j=1}^k\frac{j+2}3\sum_{i=1}^j\binom i1\\ &=\sum_{k=1}^n\frac {k+4}5\sum_{j=1}^k\frac{j+2}3\binom {j+1}2\\ &=\sum_{k=1}^n\frac {k+4}5\sum_{j=1}^k\binom {j+2}3\\ &=\sum_{k=1}^n\frac {k+4}5\binom {k+3}4\\ &=\sum_{k=1}^n\binom {k+4}5\\ &=\binom {n+5}6\qquad\blacksquare \end{align}$$
Our sum depends on three sums:
$$ S_1 =\!\!\!\!\sum_{1\leq i \leq j \leq k\leq n}\!\!\!ijk, \qquad S_2 = \!\!\!\!\sum_{1\leq i \leq j \leq k\leq n}\!\!\!ij, \qquad S_3 =\!\!\!\! \sum_{1\leq i \leq j \leq k\leq n}\!\!\!ik $$
that can be evaluated by using standard symmetry tricks. For instance:
$$ \left(\sum_{i=1}^{n} i\right)\cdot\left(\sum_{j=1}^{n} j\right)+\sum_{j=1}^{n}j^2 = 2\cdot\!\!\!\!\sum_{1\leq i\leq j\leq n}\!\!ij $$
holds, and we have a similar identity in three variables. As an alternative, $S_1$ is:
$$ S_1 = \!\!\!\!\!\!\sum_{\substack{a,b,c,d\geq 0\\a+b+c+d=n-1}}\!\!\!\!(a+1)\cdot(a+b+1)\cdot(a+b+c+1) $$
so it can be computed by expanding the general term as a sum of monomials,
then going along the following lines:
$$\begin{eqnarray*} \sum_{\substack{a+b+c+d=n-1}}\!\!\!\!\!\!\!\!a^2 b^1 c^1 d^0 &=& [x^{n-1}]\left(\sum_{n\geq 0}n^2 x^n\right)\cdot\left(\sum_{n\geq 0}n^1 x^n\right)\cdot\left(\sum_{n\geq 0}n^1 x^n\right)\cdot \left(\sum_{n\geq 0}n^0 x^n\right)\\[0.2cm]&=&[x^{n-1}]\left(\frac{x(1+x)}{(1-x)^3}\cdot\frac{x}{(1-x)^2}\cdot\frac{x}{(1-x)^2}\cdot\frac{1}{1-x}\right)\\[0.2cm]&=&[x^{n-4}]\frac{1+x}{(1-x)^8}=[x^{n-4}]\frac{1}{(1-x)^8}+[x^{n-5}]\frac{1}{(1-x)^8}\\[0.2cm]&=&\color{red}{\binom{n+3}{7}+\binom{n+2}{7}}.\end{eqnarray*}$$
One way or another, the final outcome is:
$$ \sum_{i=1}^{n}\sum_{j=i}^{n}\sum_{k=j}^{n}\frac{i(j+2)(k+4)}{15}=\color{red}{\binom{n+5}{6}}.$$
Since it is obvious that the final outcome is a polynomial in $n$ having degree $3+1+1+1=6$, also without computing it, the answer can be derived also through Lagrange interpolation: it is enough to compute the given triple sum for $n\in\{0,1,2,3,4,5,6\}$.
Addendum: the explicit way. $$\begin{eqnarray*}\sum_{1\leq i\leq j\leq k\leq n}\!\!\!i(j+2)(k+4)&=&\!\!\!\!\!\sum_{\substack{a,b,c,d\geq 0\\a+b+c+d=n-1}}\!\!\!\!\!(a+1)(a+b+3)(a+b+c+5),\end{eqnarray*} $$
$$\begin{eqnarray*}\sum_{\substack{a,b,c,d\geq 0\\a+b+c+d=n-1}}\!\!\!\!\! a^3 b^0 c^0 d^0 &=& [x^{n-1}]\frac{1}{(1-x)^3}\sum_{n\geq 0}n^3 x^n=[x^{n-1}]\frac{x(1+4x+x^2)}{(1-x)^7}\\[0.1cm]&=&[x^{n-2}]\frac{1}{(1-x)^7}+4[x^{n-3}]\frac{1}{(1-x)^7}+[x^{n-4}]\frac{1}{(1-x)^7}\\[0.25cm]&=&\binom{n+4}{6}+4\binom{n+3}{6}+\binom{n+2}{6},\\[0.3cm] \sum_{\substack{a,b,c,d\geq 0\\a+b+c+d=n-1}}\!\!\!\!\! a^2 b^1 c^0 d^0 &=& [x^{n-1}]\frac{x}{(1-x)^4}\sum_{n\geq 0}n^2 x^n=[x^{n-1}]\frac{x^2(1+x)}{(1-x)^7}\\[0.1cm]&=&[x^{n-3}]\frac{1}{(1-x)^7}+[x^{n-4}]\frac{1}{(1-x)^7}\\[0.25cm]&=&\binom{n+3}{6}+\binom{n+2}{6},\\[0.3cm] \sum_{\substack{a,b,c,d\geq 0\\a+b+c+d=n-1}}\!\!\!\!\! a^1 b^1 c^1 d^0 &=& [x^{n-1}]\frac{1}{(1-x)}\left(\sum_{n\geq 0}n x^n\right)^3=[x^{n-1}]\frac{x^3}{(1-x)^7}\\[0.1cm]&=&[x^{n-4}]\frac{1}{(1-x)^7}\\[0.25cm]&=&\binom{n+2}{6},\end{eqnarray*}$$ the remaining part is easy.
