3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Brute force works fine here. $\endgroup$
    – Mark Viola
    Apr 5, 2016 at 17:28
  • $\begingroup$ @Dr.MV - but we try to avoid it if we can :) $\endgroup$ Apr 6, 2016 at 14:37
  • $\begingroup$ 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? $\endgroup$
    – Mark Viola
    Apr 6, 2016 at 15:58
  • $\begingroup$ @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"! $\endgroup$ Apr 6, 2016 at 16:11

2 Answers 2

4
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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