Factorial Summation Definition

Question

A while back I found the series $$\sum_{k=0}^n \binom n k (-1)^k (x+k)^n = (-1)^n n!$$ while messing around in Algebra class (specifically when $n$ is any natural number and $x$ is any real number) I wrote the formula on a card, stuck it in my "to prove" box. The formula arises when subtracting subsequent powers of natural natural numbers, I.e. We start with $1^2, 2^2, 3^2, 4^2...$ and subtract subsequent terms, getting $3,5,7...$ and repeat, getting $2,2,2... = 2!$. Its well known that it takes $n$ steps using this process to get to a constant using the sequence $1^n,2^n...$, so I assume that this should be a well known theorem. I found the series written exactly like this on the OEIS, but not link was provided I could find. I have tried a number of series manipulations, but none yielded anything prettier than I started with. I considered letting $x=0$ and proving it from there (as this simplifies things), but I still couldn't quite get it. Does anyone know a proof of this using relatively elementary techniques?

Answer 1

so we would need to show that for all $j$ such that $n\ge j\gt0$ $$\sum_{k=0}^n \binom n k \binom n j (-1)^k (k)^{n-j} = 0$$ that is $$\sum_{k=0}^n \binom n k (-1)^k (k)^{n-j} = 0$$ this involves a Stirling number of second kind $$\sum_{k=0}^n \binom n k (-1)^k (k)^{n-j} =(-1)^n (n!){n-j\brace n}$$ which is $0$ since $j\gt0$

Answer 2

The identity you're seeking is closely related to finite differences. The finite differences $\Delta^1f, \Delta^2f, \Delta^3f,\ldots$ of a function $f$ are defined inductively as $$(\Delta^1f)(x) := f(x+1) -f(x)$$ and $$(\Delta^{n+1}f)(x) := \Delta^1(\Delta^nf)(x), $$ i.e. the $(n+1)$st finite difference of $f$ is the first finite difference of the $n$th finite difference of $f$, etc. As an aside, this leads to the alternative form $$ (\Delta^nf)(x) = \sum_{k=0}^n{n\choose k}(-1)^{n-k}f(x+k)\tag1 $$ which you can prove by induction.

In view of (1), the identity you're trying to prove amounts to the assertion

Claim: If $f_n(x):=x^n$, then $\Delta^nf_n$ is identically constant at $n!$.

You can prove this by induction. The case $n=1$ is clear. Suppose the claim holds for $n$. Using the Leibniz rule for the finite difference of a product (taking $\Delta^0f:=f$): $$ (\Delta^n[fg])(x) = \sum_{k=0}^n{n\choose k}(\Delta^kf)(x)(\Delta^{n-k}g)(x+k), $$ we write: $$ (\Delta^{n+1}f_{n+1})(x) =(\Delta^{n+1}[f_nf_1])(x)=\sum_{k=0}^n{n+1\choose k}(\Delta^kf_n)(x)(\Delta^{n+1-k}f_1)(x+k).$$ Since $\Delta^1f_1$ is identically equal to $1$, and $\Delta^if_1 = 0$ for $i>1$, the summation above reduces to two terms: $k=n$ and $k=n+1$, giving $$ {n+1\choose n}(\Delta^nf_n)(x)\cdot 1 + {n+1\choose n+1}(\Delta^{n+1}f_n)(x)\cdot (x+k)=(n+1)! $$ since $\Delta^nf_n=n!$ by hypothesis, which implies $\Delta^{n+1}f_n=\Delta^1(\Delta^nf_n)=0$.