12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $\alpha$ in $\mathbb{C}$? $\endgroup$ – Guido A. May 4 '18 at 5:00
  • 2
    $\begingroup$ @GuidoA. Relevant? $\endgroup$ – Did May 4 '18 at 5:17
  • 1
    $\begingroup$ 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.) $\endgroup$ – darij grinberg May 4 '18 at 6:06
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Guido A. May 4 '18 at 5:23
  • $\begingroup$ @GuidoA. Indeed you are "missing something here": what is $Q_0$? $\endgroup$ – Did May 4 '18 at 5:24
  • 1
    $\begingroup$ I see it now. Thanks! $\endgroup$ – Guido A. May 4 '18 at 5:27
  • $\begingroup$ IIRC the $Q_i$ have a special name, do you know it ? $\endgroup$ – Gabriel Romon May 4 '18 at 6:58
  • $\begingroup$ @GabrielRomon Falling factorials. $\endgroup$ – Did May 4 '18 at 9:52
3
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,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} {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}

$\endgroup$

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.