# Represent n! by binomial coefficients

I find the following formula to be true $$\sum_{k=0}^n {{n}\choose{k}}(k+1)^n(-1)^k=(-1)^nn!$$ at least for $n=1,2,3$, could any one give a proof about this in general? I'm almost sure it is true, because I use a different method to compare with a known result (in fact something of much higher level and in a very different field, the author said the result without proof, and I deduce that that result comes down to the above formula), for which I want to give an alternative proof. A good reference about this formula is preferred. I guess there should be a more general formula for which this is a special case. Thanks!

• If it were $k^n$ instead of $(k+1)^n$, I would have said inclusion-exclusion method for counting bijections $\{1,\cdots,n\}\to\{1,\cdots,n\}$ in terms of counting functions $\{1,\cdots,k\}\to\{1,\cdots,n\}$. – arctic tern May 21 '17 at 5:14

If $f(x)\in R [x]$ is a polynomial over a unital ring $R$ and the degree of $f(x)$ is at most $n$, then $$\sum_{k=0}^n\,(-1)^{n-k}\,\binom{n}{k}\,f(x+k)=n!\,a_n\,,$$ where $a_n$ is the coefficient of the $n$-th degree term of $f(x)$. To show this, try to compute $\Delta^n\,f(x)$, where $\Delta$ is the forward differencing operator: $$\Delta\,g(x):=g(x+1)-g(x)\,,$$ for $g(x)\in R[x]$. The easiest way is probably induction on $n$, noting that (1) $\Delta$ decreases the degree and (2) $\Delta^n\,f(x)=\Delta^{n-1}\,\left(\Delta\,f(x)\right)$.
• Indeed, writing the shift operator $Sf(x)=f(x+1)$, we have $\Delta^n=(S-I)^n$ which may be expanded with the binomial theorem... – arctic tern May 21 '17 at 5:15
$\newcommand{\bbx}{\,\bbox[8px,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}{n \choose k}\pars{k + 1}^{n}\pars{-1}^{k} = \sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k}\ \overbrace{\bracks{n!\oint_{\verts{z} = 1}{\expo{\pars{k + 1}z} \over z^{n + 1}}\,{\dd z \over 2\pi\ic}}}^{\ds{\pars{k + 1}^{n}}} \\[5mm] = &\ n!\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1}} \sum_{k = 0}^{n}{n \choose k}\pars{-\expo{z}}^{k}\,{\dd z \over 2\pi\ic} = n!\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1}} \pars{1 - \expo{z}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{n}\,n!\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1}}\ \overbrace{\pars{\expo{z} - 1}^{n}} ^{\ds{n!\sum_{k = 0}^{\infty}{k \brace n}{z^{k} \over k!}}}\ \,{\dd z \over 2\pi\ic}\,,\qquad \pars{\substack{\ds{i \brace j}\ \mbox{is a} \\[1mm] {\large Stirling\ Number\ of\ the\ Second\ Kind}}} \\[5mm] = &\ \pars{-1}^{n}\,\pars{n!}^{2}\sum_{k = 0}^{\infty}\!\!{k \brace n}{1 \over k!}\ \overbrace{\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1 - k}}\,{\dd z \over 2\pi\ic}}^{\ds{1 \over \pars{n - k}!}} = \pars{-1}^{n}\,\pars{n!}^{2}{n \brace n}{1 \over n!} = \bbx{\pars{-1}^{n}\,n!} \end{align}
Stirling Numbers of the Second Kind have the following relation: \newcommand{\stirtwo}{\left\{#1\atop#2\right\}} \begin{align} (k+1)^n &=\sum_{j=0}^n\stirtwo{n}{j}\binom{k+1}{j}\,j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}\left[\binom{k}{j}+\binom{k}{j-1}\right]j!\\ \end{align} Therefore, \begin{align} \sum_{k=0}^n\binom{n}{k}(k+1)^n(-1)^k &=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{j=0}^n\stirtwo{n}{j}\left[\binom{k}{j}+\binom{k}{j-1}\right]j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}\sum_{k=0}^n(-1)^k\binom{n}{k}\left[\binom{k}{j}+\binom{k}{j-1}\right]j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}\sum_{k=0}^n(-1)^k\left[\binom{n}{j}\binom{n-j}{k-j}+\binom{n}{j-1}\binom{n-j+1}{k-j+1}\right]j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}(-1)^n\big([j=n]+[j=n+1]\big)\,j!\\[9pt] &=(-1)^nn! \end{align} since $\stirtwo{n}{n}=1$, and for $j\gt n$, $\stirtwo{n}{j}=0$.