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.

  • Brute force works fine here. – Mark Viola Apr 5 '16 at 17:28
  • @Dr.MV - but we try to avoid it if we can :) – hypergeometric Apr 6 '16 at 14:37
  • Yes, of course that's true. But if one isn't aware immediately of "the trick," how long should one ponder, potentially in perpetuity, before proceeding directly? – Mark Viola Apr 6 '16 at 15:58
  • @Dr.MV - Rearranging summation indices is quite a standard move, per many other MSE questions. Once that's done the rest follows naturally. There are other much tougher olympiad-type questions which require even more non-obvious "tricks"! – hypergeometric Apr 6 '16 at 16:11

$$\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.

  • 1
    Thanks for your solution! (+1) – hypergeometric Apr 5 '16 at 23:15
  • For $n=2$ manual computation gives $7$ but the formula in the solution above gives $11.5$. – hypergeometric Apr 6 '16 at 3:29
  • @hypergeometric: you are right, there was a mistake, now fixed. – Jack D'Aurizio Apr 6 '16 at 4:59
  • Could you please elaborate a bit further on getting from the sum of monomials to the final solution? – hypergeometric Apr 6 '16 at 7:15
  • @hypergeometric: just done. – Jack D'Aurizio Apr 6 '16 at 12:24

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.