# Proving finite sum identity

I could use a hint to prove $$\sum_{k=0}^n(-1)^k {{n}\choose{k}}(\alpha+k)^n=(-1)^nn!$$

I needed that identity and found it in "Table of integrals, series, and products" by Gradshteyn et al. But just grabbing it from there is not very satisfying.

• Is $\alpha$ in $\mathbb{C}$? – Guido A. May 4 '18 at 5:00
• @GuidoA. Relevant? – Did May 4 '18 at 5:17
• This is a famous one. Equivalently, if $a$ is a nonnegative integer, and $b$ is any real, then $\sum\limits_{k=0}^a \left(-1\right)^k \dbinom{a}{k} \left(b-k\right)^a = a!$. (Your equality follows from this by setting $a = N$ and $b = \alpha+n$ and recalling the symmetry of binomial coefficients.) For a partly combinatorial proof, see Spring 2018 Math 4707 homework #3 exercise 2 (d). ("Partly" because the combinatorial interpretation works only when $b$ is an integer $\geq a$; the other cases follow by polynomiality.) – darij grinberg May 4 '18 at 6:06

## 4 Answers

The LHS is $$S_n=\sum_{k=0}^n(-1)^k {n\choose k}P(k)$$ where $P$ denotes the polynomial $$P(x)=(x+\alpha)^n$$ The key idea of the proof is that, as every polynomial of degree at most $n$, $P$ is a linear combination of the falling factorials, that is, the polynomials $$Q_i(x)=x(x-1)\cdots(x-i+1)$$ for $0\leqslant i\leqslant n$, say, $$P(x)=\sum_{i=0}^nc_iQ_i(x)$$ The rest of the proof relies on some small play on binomial coefficients.

Fix some $i$, then, for every $k<i$, $Q_i(k)=0$ and, for every $i\leqslant k\leqslant n$, $${n\choose k}Q_i(k)=\frac{n!}{k!(n-k)!}\frac{k!}{(k-i)!}=\frac{n!}{(n-i)!}\frac{(n-i)!}{(k-i)!(n-k)!}=Q_i(n){n-i\choose k-i}$$ Summing these identities on $k$ yields $$\sum_{k=0}^n(-1)^k {n\choose k}Q_i(k)=Q_i(n)\sum_{k=i}^n(-1)^k {n-i\choose k-i}=(-1)^iQ_i(n)\sum_{k=0}^{n-i}(-1)^k {n-i\choose k}$$ By the binomial theorem, the sum on the RHS is $(1-1)^{n-i}$, that is, $0$ for every $i<n$ and $1$ for $i=n$. Summing these identities on $i$, one gets $$S_n=(-1)^nQ_n(n)c_n$$ It remains to note that $Q_n(n)=n!$ and that $c_n=1$ (why?), to conclude.

• Maybe I'm missing something here, but if each $Q_i$ has $0$ as a root, that does not generate $\mathbb{R}_{\leq n}[X]$, right? – Guido A. May 4 '18 at 5:23
• @GuidoA. Indeed you are "missing something here": what is $Q_0$? – Did May 4 '18 at 5:24
• I see it now. Thanks! – Guido A. May 4 '18 at 5:27
• IIRC the $Q_i$ have a special name, do you know it ? – Gabriel Romon May 4 '18 at 6:58
• @GabrielRomon Falling factorials. – Did May 4 '18 at 9:52

For real $\beta$, define the function $\phi(\beta):=\sum\limits_{k=0}^{n}(-)^k{n\choose k}(\alpha+k)^n e^{(\alpha+k)\beta}$. So, we equivalently have $\phi(\beta)=\frac{d^n}{d\beta^n}(e^{\alpha\beta}(1-e^\beta)^n)$. Now, observe from the general Leibniz product rule that the only non-zero term for $\phi(0)$ is the term $n!e^{\alpha\beta}(-e^{\beta})^n$ (why?). We are done.

• why on earth, this answer has no upvotes so far? (+1) – tired May 5 '18 at 10:52

Seeing that

$$\sum_{k=0}^n (-1)^k {n\choose k} (\alpha+k)^n$$

is a polynomial in $\alpha$ of degree $n$ we may extract coefficients where $0\le q\le n$:

$$[\alpha^q] \sum_{k=0}^n (-1)^k {n\choose k} (\alpha+k)^n = \sum_{k=0}^n (-1)^k {n\choose k} {n\choose q} k^{n-q} \\ = {n\choose q} \sum_{k=0}^n (-1)^k {n\choose k} k^{n-q}.$$

Continuing we find

$${n\choose q} \sum_{k=0}^n (-1)^k {n\choose k} (n-q)! [z^{n-q}] \exp(kz) \\ = \frac{n!}{q!} [z^{n-q}] \sum_{k=0}^n (-1)^k {n\choose k} \exp(kz) = \frac{n!}{q!} [z^{n-q}] (1-\exp(z))^n.$$

Now since $1-\exp(z) = -z - \cdots$ we have that $(1-\exp(z))^n$ starts with $(-1)^n z^n + \cdots.$ Hence we get zero when $n-q\lt n$ or $q\gt 0.$ So all coefficients of the polynomial except the constant one vanish. For the latter we get with $q=0$ the value

$$\frac{n!}{0!} [z^n] ((-1)^n z^n + \cdots) = (-1)^n n!$$

thus proving the claim.

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