5
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Nice reference to Gould's work. $\endgroup$ – Leucippus Mar 25 '15 at 17:15
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.