Use of Bijection for computation

Question

Compute the last three digits of $$\sum_{k=1}^{2017} k^3*\binom{2017}{k}$$

I'm looking for combinatoric way to "translate" this into something much easier to compute. The Sum is the number of ways of choosing a $k$-member committee with three jobs within them (can all be the same person). I think we could do this by choosing the jobs first and then the committee. We proceed by casework on jobs.

One person has all three jobs: $2017\cdot 2^{2016}$

One person has two jobs: $2017\cdot 2016\cdot 2^{2015}$

Every job is occupied by a different person $2017\cdot 2016\cdot 2015\cdot 2^{2014}$

However if we add these cases up it is not equal to our original summation. How can I fix this? Thanks!

Answer 1

Consider $n$ people. Your three cases are:

• $\binom{n}{1}2^{n-1}$
• $\binom{n}{2}2!\binom{3}{2} 2^{n-2}$
• $\binom{n}{3}3! 2^{n-3}$

Summing these yields the identity $$\sum_{k=1}^n k^3 \binom{n}{k}=n^2(n+3)2^{n-3}$$

Now compute the right hand side $\pmod{1000}$ when $n=2017$.