Had a question on exam of enumerative combinatorics to prove the following: $$\sum_{k=0}^n k^3 {n \choose k} = (n+3)n^22^{n-3}$$ Sol'n, let us use the binomial formula: $$\sum_{k=0}^n x^k {n \choose k} = (1+x)^n$$ now take derivative:
$$\sum_{k=0}^n k x^{k-1} {n \choose k} = n(x+1)^{n-1}$$ setting x=1, let this be identity [1] $$\sum_{k=0}^n k {n \choose k} = n2^{n-1}$$ now take another derivative $$\sum_{k=0}^n k(k-1) x^{k-1} {n \choose k} = n(n-1)(x+1)^{n-2}$$ set x = 1 $$\sum_{k=0}^n (k^2-k) {n \choose k} = n(n-1)(2)^{n-2}$$ now kill the extra -k using the identity [1] by adding it $$\sum_{k=0}^n (k^2-k) {n \choose k} + \sum_{k=0}^n k {n \choose k}= n(n-1)(2)^{n-2} + n2^{n-1}$$ $$\sum_{k=0}^n (k^2) {n \choose k} = n(n+1)(2)^{n-2}$$
repeating the above procedure with derivative of order 3, and killing the extra terms will give the identity that was to be proved.
so for each $k^{1,2,3}$ we have $$\sum_{k=0}^n k {n \choose k} = n2^{n-1}$$ $$\sum_{k=0}^n k^2 {n \choose k} = n(n+1)(2)^{n-2}$$ $$\sum_{k=0}^n k^3 {n \choose k} = n^2(n+3)2^{n-3}$$
The question, is it possible to somehow solve combinatorially, say more general, $q$ fixed $$\sum_{k=0}^n k^q {n \choose k} = something$$
I used the question that was to assign the $p$ tasks to $p$ different people in the group of $k$ chosen from $n$ (some people may not have the task assigned). the formula was the following: $$\sum_{k=0}^n {k \choose p} {n \choose k} = {n \choose p}2^{n-p}$$ where on LHS we first choose a group of $k$ from $n$, then assign $p$ tasks to people in that group of k, summing up for all k, we get total number of groups. whereas on RHS we first choose people to do the tasks, then add (n-p) $\require{cancel} \cancel{slackers}$ people to that group of $tasked$ people
Now back to the question: It is to be assigned $q$ possible duties for the people from the group ${n \choose k}$, where the same person may have more than 1 duty. LHS is somehow clear, now it is left to think of the RHS.
P.S. taking further derivatives will lead to more general formula. applying for order 4 gives irrational roots, polynomial on RHS turns out to be $n(n^3+6n^2+3n-2)2^{n-4}$
Let $\def\fall(#1,#2){#1^{\underline{#2}}}\fall(k,i)$ denote $k(k-1)(k-2)\cdots (k-i+1)=k!/(k-i)!$. These are referred to as the falling factorials. Importantly, we have the following identity: $$ k^q=\sum_{i=0}^q{q\brace i}\fall(k,i), $$ where ${q\brace i}$ are the Stirling numbers of the second kind. Furthermore, $$ \fall(k,i)\binom{n}k=\fall(n,i)\binom{n-i}{k-i} $$ Therefore, \begin{align} \sum_{k=0}^n k^q\binom{n}k &=\sum_{k=0}^n\sum_{i=0}^q{q\brace i}\binom{n}k\fall(k,i) \\&=\sum_{k=0}^n\sum_{i=0}^q{q\brace i}\binom{n-i}{k-i}\fall(n,i) \\&=\sum_{i=0}^q{q\brace i}\fall(n,i)\sum_{k=0}^n\binom{n-i}{k-i} \\&=\sum_{i=0}^q{q\brace i}\fall(n,i)2^{n-i} \end{align} Using the combinatorial interpretation of the Stirling numbers, you can no doubt find a combinatorial proof of the above identity as well. Namely, ${q\brace i}$ counts the number of ways to partition a set of size $q$ into $i$ nonempty, non-distinct parts.