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

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!

• How about finding $\sum_{k=1}^n k^3\binom{n}k x^k$? – Lord Shark the Unknown Apr 21 '19 at 17:10
• I am bad with combinatorics and that is why asked how to solve the above. I am trying to understand what techniques one uses and what knowledge is required to solve it. – Elvin Jafali Apr 21 '19 at 17:11
• Well, my strategy would be to find $\sum_{k=1}^n k^3\binom{n}k x^k$ and then put $x=1$ into it. If you can't see how to do that sum, then think about $\sum_{k=1}^n k^2\binom{n}k x^k$. – Lord Shark the Unknown Apr 21 '19 at 17:17
• @LordSharktheUnknown And how would you suggest they compute that polynomial? I don't think you've made things easier from their perspective. – kccu Apr 21 '19 at 17:33

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