# 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
Stirling Numbers of the Second Kind have the following relation: \newcommand{\stirtwo}[2]{\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$.