3

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.

Hypergeometricx
  • 22,657
  • Brute force works fine here. – Mark Viola Apr 05 '16 at 17:28
  • @Dr.MV - but we try to avoid it if we can :) – Hypergeometricx Apr 06 '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 06 '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"! – Hypergeometricx Apr 06 '16 at 16:11

2 Answers2

4

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

Hypergeometricx
  • 22,657
2

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.

Jack D'Aurizio
  • 353,855