Alternating partial sums of binomial coefficients I am interested in a generalization of the partial alternating sum
$$\sum_{k=0}^{m} (-1)^k{n\choose k}=(-1)^m{n-1\choose m},\quad m<n$$
Including a factor $k^{\ell}$ for $0\leq\ell\leq n-1$
$$\sum_{k=0}^{m} k^{\ell}(-1)^k{n\choose k}$$
Mathematica can evaluate these sums, for instance the first couple are
$$\sum_{k=0}^{m} k(-1)^k{n\choose k}=(-1)^m\frac{nm}{n-1}{n-1\choose m}$$
$$\sum_{k=0}^{m} k^2(-1)^k{n\choose k}=(-1)^m\frac{nm(m(n-1)-1)}{(n-1)(n-2)}{n-1\choose m}$$
I am struggling to find a formula for general $\ell$, any help would be appreciated!
 A: Combining the factors with the binomial coefficients yields
\begin{eqnarray}
\sum_{k=0}^mk(k-1)\cdots(k-j+1)(-1)^k\binom nk
&=&
n(n-1)\cdots(n-j+1)\sum_{k=0}^m(-1)^k\binom{n-j}{k-j}
\\
&=&
n(n-1)\cdots(n-j+1)(-1)^j\sum_{k=0}^{m-j}(-1)^k\binom{n-j}k
\\
&=&
n(n-1)\cdots(n-j+1)(-1)^\ell(-1)^{m-j}\binom{n-j-1}{m-j}
\\
&=&
(-1)^m\frac n{n-j}m(m-1)\cdots(m-j+1)\binom{n-1}m\;.
\end{eqnarray}
For $j=1$ and $j=2$, this is
$$
\sum_{k=0}^mk(-1)^k\binom nk=(-1)^m\frac{nm}{n-1}\binom{n-1}m
$$
and
$$
\sum_{k=0}^mk(k-1)(-1)^k\binom nk=(-1)^m\frac{nm(m-1)}{n-2}\binom{n-1}m\;,
$$
respectively. Then
\begin{eqnarray}
\sum_{k=0}^mk^2(-1)^k\binom nk
&=&
\sum_{k=0}^m\left(k(k-1)+k\right)(-1)^k\binom nk
\\
&=&(-1)^m\frac{nm(m-1)}{n-2}\binom{n-1}m+(-1)^m\frac{nm}{n-1}\binom{n-1}m
\\
&=&(-1)^m\frac{nm(m-1)(n-1)+nm(n-2)}{(n-1)(n-2)}\binom{n-1}m
\\
&=&(-1)^m\frac{nm(m(n-1)-1)}{(n-1)(n-2)}\binom{n-1}m\;,
\end{eqnarray}
in agreement with your results from Mathematica.
For general $\ell$, the power $k^\ell$ can be expressed as a sum of falling factorials using the Stirling numbers of the second kind:
$$
k^\ell=\sum_{j=0}^\ell\left\{\ell\atop j\right\}k(k-1)\cdots(k-j+1)\;,
$$
which yields
$$
\sum_{k=0}^mk^\ell(-1)^k\binom nk=(-1)^mn\binom{n-1}m\sum_{j=0}^\ell\left\{\ell\atop j\right\}\frac{m(m-1)\cdots(m-j+1)}{n-j}\;.
$$
If it weren’t for the factor $n-j$, the sum would yield $m^\ell$, but as it is, I don’t see a way to simplify it.
A: Using the falling power notation $x^{(\mu)}=x(x-1)...(x-\mu+1))$, the forward difference notation $\Delta f(x)=f(x+1)-f(x)$ and summation by parts, we can obtain a recursive relation for $$\sum_{k=a}^bk^{(\nu)}(-1)^k{n \choose k}$$$$=\sum_{k=a}^bk^{(\nu)}\Delta (-1)^{k+1}{n-1 \choose k-1}$$ $$=k^{(\nu)} (-1)^{k+1}{n-1 \choose k-1}\vert_{k=a}^{b+1}-\nu\sum_{k=a}^bk^{(\nu -1)}(-1)^k{n-1\choose k}$$
A: We seek to evaluate
$$\sum_{k=0}^m k^\ell (-1)^k {n\choose k}.$$
This is
$$[z^m] \frac{1}{1-z} \sum_{k\ge 0} z^k k^\ell (-1)^k {n\choose k}
\\ = [z^m] \frac{1}{1-z} \ell! [w^\ell]
\sum_{k\ge 0} z^k \exp(kw) (-1)^k {n\choose k}
\\ = \ell! [w^\ell] [z^m] \frac{1}{1-z}
(1-z\exp(w))^n
\\ = \ell! [w^\ell] [z^m] \frac{1}{1-z}
(1-z-z(\exp(w)-1))^n
\\ = \ell! [w^\ell] [z^m] \frac{1}{1-z}
\sum_{k=0}^n {n\choose k} (1-z)^{n-k} (-1)^k z^k (\exp(w)-1)^k
\\ = \sum_{k=0}^n {n\choose k} {n-k-1\choose m-k}
(-1)^m k! {\ell\brace k}.$$
As a remark observe carefully that the coefficient extractor  construction
for the second binomial coefficient will produce zero when  $k\gt m$
without any kind of singularity. Continuing we note that the problem
statement says that $\ell \lt n.$ That means we get  zero from the
Stirling number when $\ell \lt k\le n.$ Hence we may set  the upper limit
to $\ell$ and get the formula (Stirling number is zero  when $k=0$):
$$\bbox[5px,border:2px solid #00A000]{
(-1)^m \sum_{k=1}^\ell {n\choose k} {n-k-1\choose m-k}
k! {\ell\brace k}.}$$
Actually we have for $k\le m$
$${n\choose k} {n-k-1\choose m-k}
= \frac{n}{n-k} {n-1\choose k} {n-k-1\choose m-k}
\\ = \frac{n}{n-k}
\frac{(n-1)!}{k! \times (m-k)! \times (n-m-1)!}
= \frac{n}{n-k} {n-1\choose m} {m\choose k}$$
so the first boxed formula simplifies to
$$(-1)^m n {n-1\choose m}
\sum_{k=1}^\ell \frac{1}{n-k} {m\choose k}
k! {\ell\brace k}.$$
Note that ${m\choose k} k! = m^{\underline{k}}$ so this is
$$\bbox[5px,border:2px solid #00A000]{
(-1)^m n {n-1\choose m}
\sum_{k=1}^\ell \frac{1}{n-k} m^{\underline{k}} {\ell\brace k}}$$
which matches the accepted answer. It also correctly produces a zero
contribution when $k\gt m.$
We get for $\ell = 3$ and $n\gt 3$
$$(-1)^m n {n-1\choose m}
\left[\frac{m}{n-1}{3\brace 1}
+ \frac{m(m-1)}{n-2} {3\brace 2}
+ \frac{m(m-1)(m-2)}{n-3} {3\brace 3} \right].$$
