Is there a much simpler proof for Euler factorial formula?

Question

Euler formula for factorial stated as follows

Theorem [Euler]: For any non negative integers $a$ and $n$ such that $a\geq n$ $$ n!=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(a-k)^n$$

Proving this formula has be asked here and the answers given there are much sophisticated. Do you know any simpler proof? or can you prove it using simple induction?

Answer 1

Consider the function $$ (1-x)^n = \sum_{k=0}^{\infty} \binom{n}{k} (-1)^k x^k. $$ Then we can write $$ \sum_{k=0}^{n} \binom{n}{k} (-1)^k k x^k = x\frac{d}{dx}\sum_{k=0}^{n}\binom{n}{k} (-1)^k x^k = x\frac{d}{dx} (1-x)^n. $$ Setting $x=1$ gives the result $$ \sum_{k=0}^{n} \binom{n}{k} (-1)^k k = 0, \quad (n>1) $$ since $$ x\frac{d}{dx} (1-x)^n = -nx(1-x)^{n-1} $$ Now, we can obviously generalise this to higher powers of $k$ by simply acting with the operator $x\frac{d}{dx}$ sufficiently many times. Linearity then allows us to extend this to polynomials in $k$ of degree $<n$. Now, this has dealt with every term in $(a-k)^n$ apart from the $k^n$ term. It is easy to see, using the operator equation $$ \frac{d}{dx}x = 1+x\frac{d}{dx}, $$ that $$ \left( x\frac{d}{dx} \right)^n = x^n \left( \frac{d}{dx} \right)^n + \text{(lower order derivatives)}; $$ as we noted above, only the first term will leave a nonzero number when we consider $$ \left( x\frac{d}{dx} \right)^n (1-x)^n, $$ evaluated at $x=1$. This term will obviously be $(-1)^n n!$, and we obtain the result $$ \sum_{k=0}^{n} (-1)^k\binom{n}{k} P(k) = (-1)^n n! a_n, $$ for polynomials $ P(k) = a_n k^n + a_{n-1} k^{n-1} + \dotsb + a_0 $.

See also Euler's formula nth Differences of Powers, H. W. Gould, The American Mathematical Monthly, Vol. 85, No. 6 (Jun. - Jul., 1978), pp. 450-467

Answer 2

Here is the simplest proof I know. It is a very straightforward application of the calculus of finite differences.

Let $f(x)$ be a polynomial. Consider its backward finite difference

$$(\Delta f)(x) = f(x) - f(x - 1).$$

Key lemma: If $f$ has leading term $a_n x^n$, then $\Delta f$ has leading term $n a_n x^{n-1}$. In particular, its degree is one less than that of $f$.

Sketch. Just expand out $f(x) - f(x - 1)$ using the binomial theorem. Notice that this is exactly how the derivative behaves, which is one reason it's nice: it's quite easy to remember. $\Box$

Now, write $\Delta^n f$ for the $n$-fold finite difference of $f$.

Corollary: If $f$ has leading term $x^n$, then $\Delta^n f = n!$.

On the other hand, what is $\Delta^n f$ more explicitly? Write $S$ for the operator which, given a function $f(x)$, returns the function $f(x - 1)$, and write $I$ for the identity operator which, given a function $f(x)$, returns the function $f(x)$ again. Then the backward finite difference can be written

$$\Delta f = (I - S) f$$

and hence, by the binomial theorem,

$$\Delta^n f = (I - S)^n f = \sum_{k=0}^n {n \choose k} (-1)^k S^k f$$

or, more explicitly,

$$(\Delta^n f)(x) = \sum_{k=0}^n {n \choose k} (-1)^k f(x - k).$$

You can also prove this identity by induction or using generating functions. However you want to prove it, once you combine it with the corollary above, setting $f(x) = x^n$ gives exactly the desired result.