We start with the identity $\sum_{k=0}^n \binom{k}{j} \binom{n}{k}=\sum_{k=0}^n \binom{n}{j} \binom{n-j}{k}=\binom{n}{j}2^{n-j}$. Then we want to decompose $k^j$ as a linear combination of the binomial coefficients $\binom{k}{i}$ for $i \le j$. This decomposition is uniquely given by the Stirling Numbers of the Second Kind: \[k^j=\sum_{i=0}^j {j\brace i} i! \binom{k}{j}\]But as we shall see, we really don't need any information about these coefficient except that they exist (which is obvious since both the powers $X^j$ and the "binomial function" $\binom{X}{j}$ form a basis of the polynomial ring $\mathbb{Z}[X]$) and that they are non-negative (which can easily be established combinatorially). We then find that \[\sum_{k=0}^n k^j\binom{n}{k}=\sum_{k=0}^n \sum_{i=0}^j {j\brace i} i! \binom{k}{i}\binom{n}{k}=\sum_{i=0}^j {j\brace i} i! \binom{n}{i}2^{n-i} \ge 2^{n-j} \sum_{i=0}^j {j\brace i} i! \binom{n}{i}=2^{n-j}n^j.\]

Here is a combinatorial proof. Consider the following question: Quote: In a competition with $n$ people, $k$ of them are selected for a team. As a reward, $j$ gifts are to be distributed among them (a single person may receive multiple gifts.) How many ways are there of choosing this? Clearly, there are $\binom{n}{k}$ ways of choosing the team members, and $k^j$ ways to distribute the gifts. So the answer to the above question is just $\sum_{k=0}^nk^j\binom{n}{k}$, or the LHS in the problem. To bound this, consider choosing the $j$ gift-receivers first. Since there are $n$ people, there are $n^j$ ways to initially distribute the gifts. Then if $j<n$, there are $2^{n-j}$ ways of choosing the remaining team members, giving a total of $2^{n-j}n^j$ possibilities. If $j\geq n$, then all $n$ people are in the team, giving a total of $n^j$ possibilities - which, in this instance, is greater than $2^{n-j}n^j$ since $n-j \leq 0$. Hence, in either case, the LHS is bounded below by the RHS, proving the desired inequality.