Compute $\sum \limits_{k=0}^{n}(-1)^{k}k^{m}\binom{n}{k}$ using Lagrange interpolation.

Question

Using Lagrange interpolation (I think identity $\sum \limits_{k=0}^{n}k^{m}\prod \limits_{\substack{i=0\\i\neq k}}^{n}\frac{x-i}{k-i}=x^m$) shows that

$$\sum \limits_{k=0}^{n}(-1)^{k}k^{m}\binom{n}{k}=0 \text{ if }\ 0≤m<n$$

and $$\sum \limits_{k=0}^{n}(-1)^{k}k^{n}\binom{n}{k}=(-1)^{n}n!$$ (same sum with $m=n$).

EDIT: I found it quite straightforward to prove first equality (just put x=0 into identity), the second part is definitely harder.

Answer 1

I thought it might be instructive to present an alternative approach. Using the binomial theorem, we can write

$$(1-x)^n=\sum_{k=0}^n\binom{n}{k}(-1)^{k}x^k\tag 1$$

---

Differentiating $(1)$ with respect to $x$ and multiplying the result by $x$ yields

$$\begin{align} x\frac{d}{dx}\left((1-x)^n\right)&=-nx(1-x)^{n-1}\tag2\\\\ &=\sum_{k=0}^n\binom{n}{k}(-1)^{k}kx^k \tag3 \end{align}$$

Setting $x=1$ in $(2)$ and $(3)$ reveals

$$\sum_{k=0}^n\binom{n}{k}(-1)^{k}k=0$$

provided $n>1$. And if $n=1$, then we find that $\sum_{k=0}^1\binom{1}{k}(-1)^kk^1=1$.

---

We can repeat this process to obtain

$$\left.\left(\left(x\frac{d}{dx}\right)^m (1-x)^n\right)\right|_{x=1}=\sum_{k=0}^n\binom{n}{k}(-1)^{k}k^m \tag 4$$

So, the problem boils down to showing that the left-hand side of $(4)$ is $0$ for $m<n$ and $(-1)^n\,n!$ for $n=m$. To do so, we use induction.

We claim that we can write

$$\left(x\frac{d}{dx}\right)^m (1-x)^n=\sum_{\ell=1}^m p_\ell(x)(1-x)^{n-\ell} \tag {5a}$$

where $p_\ell(x)$ is a polynomial of order $\ell$ with

$$p_m(x)=(-1)^m m!\binom{n}{m}x^m \tag {5b}$$

---

Proving $(5)$ by induction

From $(1)$, we see that a base case to prove $(5)$ inductively is established. Then, assuming $(5)$ is true for some $m>1$, we have

$$\begin{align} \left(x\frac{d}{dx}\right)^{m+1}(1-x)^{n+1}&=x\frac{d}{dx}\sum_{\ell=1}^m p_\ell(x)(1-x)^{n-\ell}\\\\ &=\sum_{\ell=1}^m \left(xp_\ell'(x)(1-x)^{n-\ell}-(n-\ell)xp_\ell(x)(1-x)^{n-\ell-1}\right)\\\\ &=\sum_{\ell=1}^{m+1} q_\ell(x)(1-x)^{n-\ell} \end{align}$$

where the terms $q_\ell(x)$ are given by

$$q_\ell(x)=\begin{cases}xp_\ell'(x)&,\ell=1\\\\ xp_\ell'(x)-(n-\ell+1)xp_{\ell-1}(x)&,1<\ell\le m\\\\ -(n-m)xp_{m}(x)&,\ell=m+1 \end{cases}$$

Furthermore, we see that

$$\begin{align} q_{m+1}(x)&=(-1)(n-m)xp_m(x)\\\\ &=(-1)^{m+1}(n-m)m!\binom{n}{m}\\\\ &=(-1)^{m+1}(m+1)!\binom{n}{m+1} \end{align}$$

And we have proven inductively that the relationships in $(5)$ hold.

---

Finally, using $(5)$ in $(4) yields

$$\sum_{k=0}^n\binom{n}{k}(-1)^{k}k^m =\begin{cases}0,n>m\\\\(-1)^n\,n!&,n=m\end{cases}$$

Answer 2

It can be easily proven using partial fraction expansion. Since this expansion is entailed by Lagrange's interpolation formula for the numerator, it may give you an interesting view of the problem.

For $0 \leqslant m \leqslant n$ we have the expansion \begin{equation} \frac{t^{m}}{t(t+1)\dotsm(t+n)}=\sum_{k=0}^{n}{\frac{c_{k}}{t+k}}.\label{eq}\tag{E} \end{equation} You get $c_{k}$ by multiplying by $t+k$ and then evaluate at $-k$, which gives: $$\frac{k^{m}}{(k)(k-1)\dotsm (1)(-1)\dotsm(-(n-k))}=c_{k}$$ that is $c_{k}=(-1)^{n-k}\binom{n}{k}\frac{k^{m}}{n!}$. Multiply the expansion \eqref{eq} by $t$ and have $t \to +\infty$ to get $$\sum_{k=0}^{n}{c_{k}}=\begin{cases}0&\text{if $m<n$}\\1&\text{if $m=n$}\end{cases}$$ and you're done!

Now, the link with Lagrange's interpolation: if you write the interpolation formula at points $-n,\dotsc,-1,0$ you get: $$t^{m}=\sum_{k=0}^{n}{\left((-k)^{m}\prod_{\substack{i=0\\i \neq k}}^{n}{\frac{t+i}{-k+i}}\right)}$$ Divide by $t(t+1)\dotsm(t+n)$ to recognize the partial fraction expansion above.

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 0}^{n}\pars{-1}^{k}\,k^{m}{n \choose k} & = \sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k}\bracks{% m!\oint_{\verts{z} = 1}{\exp\pars{kz} \over z^{m + 1}}\,{\dd z \over 2\pi\ic}} \\[5mm] & = m!\oint_{\verts{z} = 1}{1 \over z^{m + 1}} \sum_{k = 0}^{n}{n \choose k}\pars{-\expo{z}}^{k}\,{\dd z \over 2\pi\ic} = m!\pars{-1}^{n}\oint_{\verts{z} = 1}{\pars{\expo{z} - 1}^{n} \over z^{m + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] & = m!\pars{-1}^{n}\oint_{\verts{z} = 1}{1 \over z^{m + 1}} \bracks{n!\sum_{k = 0}^{\infty}{k \brace n}{z^{k} \over k!}} \,{\dd z \over 2\pi\ic} = \bbx{\ds{\pars{-1}^{n}\,n!}\,{m \brace n}} \end{align}

$\ds{a \brace b}$ is a Stirling Number of the Second Kind.