I have come across the following identity that involves binomial coefficients $\binom{n}{k}$, Stirling numbers of the second kind $\left\{ m \atop j \right\}$ and generalized hypergeometric series $_p F_q(a_0, a_1, …, a_p; b_0, b_1, …, b_q; z)$.
$$\begin{align}
\sum_{k=0}^n k^a \binom{n}{k}
&= n\ _a F_{a-1}(2, 2, …, 2, 1 – n;1, 1, …, 1; -1)\\
&=2^{n-m}\sum_{j=0}^m\binom{n}{j}2^{m-j} \left\{ m \atop j \right\} j!\\
\end{align}$$
How on earth does this work? The link between the first two parts of the identity is conjectured in one of my previous questions here and the link between the first and third parts of the identity are detailed in the answers to this question. But if I was given the second and third parts of the identity, I wouldn't know how to describe it, let alone prove it.
Any advice or suggestions welcome.
Best Answer
We can start with the hypergeometric
$$n \, _a F_{a-1} (2,2,\ldots,2,1-n;1,1,\ldots;-1)$$
and obtain
$$n \sum_{m\ge 0} \frac{(-1)^m}{m!} \frac{(m+1)!^{a-1}}{m!^{a-1}} {1-n+m-1\choose m} m! \\ = n \sum_{m=0}^n (-1)^m (m+1)^{a-1} {m-n\choose m} \\ = n \sum_{m=0}^n (m+1)^{a-1} {n-1\choose m} \\ = n \sum_{m=1}^{n+1} m^{a-1} {n-1\choose m-1} = \sum_{m=0}^n m^a {n\choose m}.$$
For the second equality we can start from
$$2^n \sum_{j=0}^a {n\choose j} 2^{-j} {a\brace j} j!$$
getting with the usual EGF
$$2^n \sum_{j=0}^a {n\choose j} 2^{-j} a! [z^a] (\exp(z)-1)^j \\ = 2^n a! [z^a] \sum_{j\ge 0} {n\choose j} 2^{-j} (\exp(z)-1)^j.$$
Here we have extended to infinity due to the coefficient extractor in $[z^a]$ and the fact that $(\exp(z)-1)^j = z^j+\cdots$. Continuing,
$$2^n a! [z^a] (1+(\exp(z)-1)/2)^n = a! [z^a] (\exp(z)+1)^n \\ = a! [z^a] \sum_{m=0}^n {n\choose m} \exp(mz) = \sum_{m=0}^n {n\choose m} m^a.$$
This is the claim.