# Evaluating complicated sum

Evaluate for a fixed $m\neq 1$ ( $m\in \mathbb{N}$ )

$$\sum _{k=1}^{n}\left[\left( \sum _{i=1}^{k}i^{2}\right) \left(\sum _{k_{1}+k_{2}+...+k_{m}=k}\dfrac {\left( k_{1}+k_{2}+\ldots +k_{m}\right) !} {k_{1}!k_{2}!...k_{m}!}\right)\right]$$

-
Note that the last part of your summation: $$\sum_{k_{1}+k_{2}+\cdots+k_{m}=k}{\frac{k!}{k_{1}!k_{2}!\cdots k_{m}!}}=\sum_{k_{1}+k_{2}+\cdots+k_{m}=k}{{k \choose k_{1},k_{2},\cdots,k_{m}}}$$ Where ${k \choose k_{1},k_{2},\cdots,k_{m}}$ is the multinomial co-efficient. –  Shaktal Jul 23 '12 at 10:49
Is your innermost sum (1) over all $m$-vectors of natural numbers whose sum of components is $k$, (2) over all $m$-vectors of positive integers whose sum of components is $k$, (3) over all $m$-component partitions of $k$, or (4) something else? –  John Bentin Jul 23 '12 at 10:57

Note that the last part of your summation:

$$\sum_{k_{1}+k_{2}+\cdots+k_{m}=k}{\frac{k!}{k_{1}!k_{2}!\cdots k_{m}!}}=\sum_{k_{1}+k_{2}+\cdots+k_{m}=k}{{k \choose k_{1},k_{2},\cdots,k_{m}}}$$

Where ${k \choose k_{1},k_{2},\cdots,k_{m}}$ is the multinomial co-efficient.

Therefore, we can immediately evaluate this, due to the following theorem:

$$\sum_{k_{1}+k_{2}+\cdots+k_{m}=k}{{k \choose k_{1},k_{2},\cdots,k_{m}}}=m^{k}$$

So we now have:

$$\sum_{k=1}^{n}{\left[\left(\frac{k(k +1)(2k+1)}{6}\right)\left(m^{k}\right)\right]}=\sum_{k=1}^{n}{m^{k}\left(\frac{k}{6}+\frac{k^{2}}{2}+\frac{k^{3}}{3}\right)}=\sum_{k=1}^{n}{\frac{m^{k}k}{6}}+\sum_{k=1}^{n}{\frac{m^{k}k^{2}}{2}}+\sum_{k=1}^{n}{\frac{m^{k}k^{3}}{3}}$$

Which has no nice expansion, but mathematica yields the following:

$$\frac{1}{6 (-1+m)^4}m (6+6 m-6 m^n-6 m^{1+n}-13 m^n n+15 m^{1+n} n-3 m^{2+n} n+m^{3+n} n-9 m^n n^2+21 m^{1+n} n^2-15 m^{2+n} n^2+3 m^{3+n} n^2-2 m^n n^3+6 m^{1+n} n^3-6 m^{2+n} n^3+2 m^{3+n} n^3)$$

Hope this helps!

-
The textbook give (only) an answer: $$(\dfrac {1} {3\left( m-1\right) }n^{3}+\dfrac {m-3} {2\left( m -1\right) ^{2}}n^{2}+\dfrac {m^{2}-2m+13} {6\left( m-1\right) ^{3}}n-\dfrac {m+1} {\left( m-1\right) ^{4}})m^{n+1}+\dfrac {m\left( m+1\right) } {\left( m-1\right) ^{4}}$$ –  Maria Mikolayevskaya Jul 23 '12 at 12:00
As Shaktal showed earlier it is remains to find closed form for $$\sum\limits_{k=1}^n\frac{m^k k^3}{3}$$
Consider the following equality $$\sum\limits_{k=1}^n x^k=\frac{x(x^n-1)}{x-1}$$ After triple differentiation we get $$\sum\limits_{k=1}^n kx^{k-1}=\frac{d}{dx}\frac{x(x^n-1)}{x-1}\\ \sum\limits_{k=1}^n k(k-1)x^{k-2}=\frac{d^2}{dx^2}\frac{x(x^n-1)}{x-1}\\ \sum\limits_{k=1}^n k(k-1)(k-2)x^{k-3}=\frac{d^3}{dx^3}\frac{x(x^n-1)}{x-1}$$ Now let's make a small trick $$\sum\limits_{k=1}^n\frac{k^3 x^k}{3}= \frac{1}{3}\sum\limits_{k=1}^n (k (k-1)(k-2)+3k(k-1)+k)x^k= \frac{1}{3}\left(x^3\sum\limits_{k=1}^n k (k-1)(k-2)x^{k-3} +3x^2\sum\limits_{k=1}^n k(k-1)x^{k-2} +x\sum\limits_{k=1}^n k x^{k-1} \right)= \frac{1}{3}\left(x^3\frac{d^3}{dx^3}\frac{x(x^n-1)}{x-1} +3x^2\frac{d^2}{dx^2}\frac{x(x^n-1)}{x-1} +x\frac{d}{dx}\frac{x(x^n-1)}{x-1} \right)$$ It is remains to simplify this expression (i.e. differentiante) and then substitute $x=m$