Find the summation of given expression: $\sum_{k=1}^n k^3\binom nk$

Question

I am trying to solve the following question which is Ex3 from Arthur Engel, Problem Solving strategies. Here is the question: $\sum_{k=1}^n k^3 {n \choose k}$ and asks to find the sum. I am sincerely having a hard time trying to figure out how to solve it and get $n^2 (n+3)(2)^{n-3}$. I would really appreciate if someone could show the step-by-step process. Thank you!

Answer 1

Let $k^3=k(k-1)(k-2)+ak(k-1)+ bk$

$\implies k=1,b=1$

$k=2,2^3=2a+2b\iff a=3$

Now for $k>2, $ $$k(k-1)(k-2)\binom nk=n(n-1)(n-2)\binom{n-3}{k-3}$$

Similarly $k\binom nk=?$

$k(k-1)\binom nk=?$

Finally use $(a+b)^m=\sum_{r=0}^n\binom mra^{m-r}b^r$

Set $a=b=1, m=n-3,n-2,n-1$

Answer 2

Expanding on @LordSharktheUnknown's hint (since a duplicate of this question was recently posted), apply $x\frac{d}{dx}$ thrice to $\sum_{k=1}^n\binom{n}{k}x^k=(1+x)^n$. First,$$\sum_k\binom{n}{k}kx^k=nx(1+x)^{n-1}=n(1+x)^n-n(1+x)^{n-1}.$$Second,$$\begin{align}\sum_k\binom{n}{k}k^2x^k&=n^2x(1+x)^{n-1}-n(n-1)x(1+x)^{n-2}\\&=n^2(1+x)^n-(2n^2-n)(1+x)^{n-1}+n(n-1)(1+x)^{n-2}.\end{align}$$Third,$$\sum_k\binom{n}{k}k^3x^k=n^3x(1+x)^{n-1}-(2n^2-n)(n-1)x(1+x)^{n-2}+n(n-1)(n-2)x(1+x)^{n-3}.$$The case $x=1$ simplifies to $\sum_k\binom{n}{k}k^3=n^2(n+3)2^{n-3}$.

Answer 3

We can use the following:

$$ \begin{aligned} \sum_{k=0}^{n}{\binom{n}{k}k^{3}}&=3!\binom{n}{3}\sum_{k=3}^{n}{\binom{n-3}{k-3}}+6\binom{n}{2}\sum_{k=2}^{n}{\binom{n-2}{k-2}}+\binom{n}{1}\sum_{k=1}^{n}{\binom{n-1}{k-1}}\\ \\ &=2^{n-3}\left(n^{3}-3n^{2}+2n\right)+3\ 2^{n-2}\left(n^{2}-n\right)+2^{4}n\\ \\ &=2^{n-3}\left(n^{3}+3n^{2}\right) \end{aligned} $$

LHS: choosing $k$ engineers from $n$ people then choosing production, maintenance, and research manager from them. One person can hold many title.

RHS: choosing production, maintenance, and research manager from $n$ people, then choose engineers from the remaining people to make $k$ total of engineers and managers.