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!

  • $\begingroup$ How about finding $\sum_{k=1}^n k^3\binom{n}k x^k$? $\endgroup$ – Lord Shark the Unknown Apr 21 '19 at 17:10
  • $\begingroup$ 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. $\endgroup$ – Elvin Jafali Apr 21 '19 at 17:11
  • $\begingroup$ 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$. $\endgroup$ – Lord Shark the Unknown Apr 21 '19 at 17:17
  • $\begingroup$ @LordSharktheUnknown And how would you suggest they compute that polynomial? I don't think you've made things easier from their perspective. $\endgroup$ – 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$


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.