$m=\sum_{k=1}^{2017}k^3\binom{n}{k}$. Find m.

Question

$$m=\sum_{k=1}^{2017}k^3\binom{n}{k}$$

Find m.

I was given this question for a math class I'm taking and I don't really know how to start or what identities to use. Could someone give me a hint?

Answer 1

Let $B_k(n) = \sum_{j=0}^k \begin{pmatrix} n \\ j \end{pmatrix}.$

$$m = 2017^3 - \sum_{k=0}^{2016} B_k(n) (3k^2 + 3k + 1).$$

Now sum by parts another couple of times ...

Answer 2

The problem seems to mix up $n$ and $2017$ somehow. We can show \begin{align*} \sum_{k=1}^nk^3\binom{n}{k}=2^{n-3}n^2(n+3)\tag{1} \end{align*} and a special case is evaluating (1) at $n=2\,017$.

We obtain \begin{align*} \color{blue}{\sum_{k=1}^n}&\color{blue}{k^3\binom{n}{k}}=n\sum_{k=1}^nk^2\binom{n-1}{k-1}\tag{2}\\ &=n\sum_{k=1}^{n}\left((k-1)(k-2)+3(k-1)+1\right)\binom{n-1}{k-1}\tag{3}\\ &=n\sum_{k=3}^{n}(k-1)(k-2)\binom{n-1}{k-1} +3n\sum_{k=2}^{n}(k-1)\binom{n-1}{k-1}+n\sum_{k=1}^{n}\binom{n-1}{k-1}\tag{4}\\ &=n(n-1)(n-2)\sum_{k=3}^{n}\binom{n-3}{k-3} +3n(n-1)\sum_{k=2}^{n}\binom{n-2}{k-2}+n\sum_{k=1}^{n}\binom{n-1}{k-1}\tag{5}\\ &=n(n-1)(n-2)\sum_{k=0}^{n-3}\binom{n-3}{k} +3n(n-1)\sum_{k=0}^{n-2}\binom{n-2}{k}+n\sum_{k=0}^{n-1}\binom{n-1}{k}\tag{6}\\ &=n(n-1)(n-2)2^{n-3}+3n(n-1)2^{n-2}+n2^{n-1}\tag{7}\\ &\,\,\color{blue}{=2^{n-3}n^2(n+3)} \end{align*} and the claim (1) follows.

Comment:

• In (2) we use the binomial identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$.

• In (3) we represent $k^2$ as polynomial in $k-1$ and $k-2$ as preparation for the next steps.

• In (4) we multiply out and set the lower limits accordingly skipping zero terms.

• In (5) we repeatedly apply the binomial identity from (2) again.

• In (6) we shift the indices to start with $k=0$.

• In (7) we use the binomial identity $(1+1)^q=2^q$ and simplify the expression in the last step.