I'm trying to find a general closed-form expression for the following sum:

$$m_p(N) = \sum_{n=0}^{N} \binom{N}{n} n^p$$

where $N,p\ge 0$ are integers.

So far I've been able to evaluate:

$$ \begin{eqnarray*} \sum_n \binom{N}{n} n^0 & = & 2^N\\ \sum_n \binom{N}{n} n^1 & = & 2^{N - 1} N\\ \sum_n \binom{N}{n} n^2 & = & 2^{N - 2} (N + 1) N\\ \sum_n \binom{N}{n} n^3 & = & 2^{N - 3} (N + 3) N^2 \end{eqnarray*} $$

but I don't see a general pattern here.

Is there a general analytical expression?

Note that this is not a textbook exercise. I'm not sure if a solution exists.

  • $\begingroup$ There is a formula which uses the Stirling numbers of both kinds, or Stirling numbers of the second kind and falling factorials. Use the formula $n^p = \sum {p\brace k}(n)_k$, then use the technique in drhab’s answer. If you like, you can use $(N)_k=\sum {k\brace i}N^i$ to get a formula in powers of $N$. $\endgroup$ – Mike Earnest Jan 17 at 17:00

The following equality might be helpful:


Here $\left(x\right)_{p}$ is a notation for $x\left(x-1\right)\cdots\left(x-p+1\right)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.