Let S denote the set of triples (i,j,k) such that i + j + k = n.
Evaluate \displaystyle \sum_{(i,j,k) \in S} ijk.
[originally posted by und on TSR]
2 Likes
i,j,k\in\mathbb{N}_0? (i guess i,j,k\in\mathbb{N} would also suffice in the context)
It isn’t specified, I’d roll with whatever makes more sense.
2 Likes
i’ll assume that i,j,k\in\mathbb{N}_0 and (i,j,k) is an ordered triple (eg. (1,2,0)\not\equiv(0,2,1))
WLOG consider i as it varies. firstly as a sub-problem (for ease of understanding) fix i=0\implies j+k=n. now this sub-problem reduces to finding all unordered pairs (j,k) such that j+k=n, to then find jk for each.
notice that if j+k=N for some N\in\mathbb{N}, then \exists \ N+1 such pairs, which are (0,N),(1,N-1),(2,N-2),\ldots,(N-1,1),(N,0). so the sum of all our jk is given by, generally as N varies
\sum_{j=0}^{N}j(N-j)
for i=0 we have N=n, and the desired sum will be
0\times\sum_{j=0}^{n}j(n-j)
now the sub-problem can easily be generalised to the main problem, as all that is different is that as i varies, we must vary N with it. specifically, if i=b then N=n-b. so we will obtain a double sum.
\begin{align}
\therefore \sum_{(i,j,k)\in S}ijk
&=\sum_{i=0}^{n}i\sum_{j=0}^{n-i}j(n-i-j)
\\ &=\sum_{i=0}^{n}i\left((n-i)\sum_{j=0}^{n-i}j-\sum_{j=0}^{n-i}j^2\right)
\\ &= \sum_{i=0}^{n}i\left((n-i)(\frac 1 2 (n-i)(n-i+1))-\frac 1 6 (n-i)(n-i+1)(2(n-i)+1)\right)
\\ &= \sum_{i=0}^{n}i\left(\frac 1 2 (n-i)^2(n-i+1)-\frac 1 6 (n-i)(n-i+1)(2n-2i+1)\right)
\\ &= \sum_{i=0}^{n}i\left(\frac 1 6 (n-i)(n-i+1)(3(n-i)-(2n-2i+1))\right)
\\ &= \frac 1 6 \sum_{i=0}^{n}i(n-i)(n-i+1)(n-i-1)
\\ &= \frac 1 6 \sum_{i=0}^{n}i(n-i)((n-i)^2-1)
\\ &= \frac 1 6 \sum_{i=0}^{n}i((n-i)^3-(n-i))
\\ &= \frac 1 6 \sum_{i=0}^{n}i(n^3-3n^2i+3ni^2-i^3-n+i)
\\ &= \frac 1 6 \sum_{i=0}^{n}n(n+1)(n-1)i+(1-3n^2)i^2+3ni^3-i^4
\\ &= \frac 1 6 n(n+1)(n-1) \sum_{i=0}^{n}i+\frac 1 6 (1-3n^2) \sum_{i=0}^{n}i^2+\frac 1 2 n \sum_{i=0}^{n}i^3- \frac 1 6 \sum_{i=0}^{n}i^4
\\ &= \frac 1 {12} n^2(n+1)^2(n-1)+\frac 1 {36} n(n+1)(2n+1)(1-3n^2)+\frac 1 {8} n^3(n+1)^2 - \frac 1 {180} n(n+1)(2n+1)(3n^2+3n-1)
\\ &= (\frac 1 {12} n^5 + \frac 1 {12} n^4 - \frac 1 {12} n^3 - \frac 1 {12} n^2) + (-\frac 1 {6} n^5 - \frac 1 {4} n^4 - \frac 1 {12} n^2 + \frac 1 {36} n) + (\frac 1 {8} n^5 + \frac 1 {4} n^4 + \frac 1 {8} n^3) - (\frac 1 {30} n^5 + \frac 1 {12} n^4 +\frac 1 {18} n^3 -\frac 1 {180} n)
\\ &= \frac{1}{120}n^5-\frac{1}{24}n^3+\frac{1}{30}n
\\ &= \frac{1}{120}n(n^4-5n^2+4)
\\ &= \frac{1}{120}n(n^2-1)(n^2-4)
\\ &= \frac{1}{120}n(n+1)(n-1)(n-2)(n+2)
\end{align}
i also just noticed that the result is a product of 5 consecutive numbers, and because 120 is a factorial you can rewrite this v neatly as \displaystyle\frac{(n+2)!}{(n-3)!5!}=\binom{n+2}{5}
3 Likes
Do you mean:
\displaystyle \frac {(n + 2)!} {(n - 3)! 5!} = \binom {n + 2} 5
(having (n - 2)! on the denominator would cancel the n - 2 term too and 120 = 5!)
Otherwise, nice solution!
1 Like
yep oops you’re right sry, think it was like 3am when i “noticed” that so i’m not surprised it was off 
i remember thinking 4!=120 for some reason, thanks i’ll edit it
any ideas on where the binomial term comes out from? seems a rly unexpected result out of taking the sum of the products
Well when I first saw the question I thought some kind of binomial expansion (would make sense with the binomial coefficient) since that’s where you often see terms like \displaystyle \sum_{i + j + k = n} (\ldots) but I drew a blank from there.
There might be some very nice combinatorial way of just writing down the answer with a line of working (seeing the answer’s so simple) and if that’s the case I’d love to see it lol.
1 Like
ooh interesting, true that could be linked to it. i’ll give it some thought as well ((: