# Is there a much simpler proof for Euler factorial formula?

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?

• Have you followed all the answers ? – lab bhattacharjee Mar 25 '15 at 16:40
• @labbhattacharjee: Sure. There are five answers most of them are analytic proofs and one combinatorial proof? am I right? – albo Mar 25 '15 at 16:45
• There are several proofs at this MSE link including a compact one using complex variables. – Marko Riedel Mar 25 '15 at 20:31

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

• Nice reference to Gould's work. – Leucippus Mar 25 '15 at 17:15

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.