# Computing a finite binomial sum

I want to compute $$S(n,m,a)=\sum_{k=0}^{n}k^{m}\cdot\binom{n}{k}\cdot a^k.$$ With $n,m\in\mathbb N$, $a\neq0$ and $S(n,0,a)=(a+1)^n$.

I don't see any other options then integrating until we've got Newton's formula and then differentiating it as many times as we integrated.

I have found some values:$$S(n,1,a)=na\cdot(a+1)^{n-1}$$ $$S(n,2,a)=an(an+1)(a+1)^{n-2}$$ $$S(n,3,a)=an(a^2n^2+3an-a+1)(a+1)^{n-3}.$$

And, since $\displaystyle\sum_{k=0}^{n}k^{m}\cdot\binom{n}{k}a^k=a\cdot\frac{\mathrm d}{\mathrm da}\int\displaystyle\sum_{k=0}^{n}k^{m}\cdot\binom{n}{k}a^{k-1}\mathrm da=a\cdot\frac{\mathrm d}{\mathrm da}\sum_{k=0}^{n}k^{m-1}\cdot\binom{n}{k}a^k$, I have the recursion $$S(n,m,a)=a\cdot\frac{\mathrm d}{\mathrm da}S(n,m-1,a).$$ But I can't find any general formula.

-
The verb corresponding to the noun "derivative" is "differentiate". – joriki Oct 29 '12 at 15:32
If your reasonning is correct, then $S(n,2,a)=a\cdot\frac{\mathrm d}{\mathrm da}S(n,1,a)=na(n-1)(a+1)^{n-2}$ – wnvl Oct 29 '12 at 17:19
Just a small remark, I think you forgot the summation just before ",I have the recursion" – wnvl Oct 29 '12 at 17:22
Maybe it might help that $$S(n,m,a_1)=n\cdot\frac{\mathrm d}{\mathrm da_1}\left(\left.\frac{\mathrm d}{\mathrm da_2}\left(...\left.\frac{\mathrm d}{\mathrm da_m}\left(\left(1+\prod_{k=1}^{m}a_k\right)^{n-1}\cdot\prod_{k=1}^{m}a_k\right)‌​\right|_{a_m=1}...\right)\right|_{a_2=1}\right)$$ – barto Oct 29 '12 at 18:24
@wnvl: The reasoning is right, but $S(n,1,a)=na(a+1)^{n-1}$. – barto Oct 29 '12 at 19:12

The following is not a complete solution. The sum is reduced to a sum over $m$ rather than $n+1$ terms. Let $D = \partial/\partial a$. Then $$\begin{eqnarray*} S(n,m,a) &=& \sum_{k=0}^n {n\choose k} k^m a^k \\ &=& (a D)^m \sum_{k=0}^n {n\choose k} a^k \\ &=& (a D)^m (1+a)^n \\ &=& \left(\sum_{k=1}^m \left\{m\atop k\right\} a^k D^k\right)(1+a)^n \\ &=& \sum_{k=1}^m \left\{m\atop k\right\} a^k \frac{n!}{(n-k)!} (1+a)^{n-k} \end{eqnarray*}$$ Therefore, $$S(n,m,a) = n!(1+a)^n \sum_{k=1}^m \left\{m\atop k\right\} \frac{1}{(n-k)!} \left(\frac{a}{1+a}\right)^k.$$ The operator $(a D)^m$ and its relation to the Stirling numbers of the second kind is dealt with here.