Elementary Proof of sum of alternating factorials

Question

so I came across the rather interesting identity

$$ \sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x-j)\right] \right] = x! $$

For positive integers $x$.

This expands to:

$$\left(\frac{1}{0!}\right) + \left(\frac{1}{0!}- \frac{1}{1!}\right)x + \left(\frac{1}{0!}- \frac{1}{1!} + \frac{1}{2!}\right) x(x-1) + \left(\frac{1}{0!}- \frac{1}{1!} + \frac{1}{2!} -\frac{1}{3!} \right)x(x-1)(x-2) ... = x!$$

How do you prove this in an elementary setting?

My current proof for this identity is pretty peculiar and uses a lot of non trivial tools from the calculus of finite differences.

Particularly it involves exploring the functional equation

$$f(x+1) = xf(x), \ f(0) = 1 \rightarrow f(x) = x!$$ Which can be refactored as

$$f(x+1) - f(x) = (x-1)f(x)$$

Now using my own "Q" notation such that

$$Q_w\left[ f(x) \right] = \lim_{h \rightarrow w} \frac{f(x+h) - f(x)}{h}$$

We write:

$$Q_1[f(x)] = (x-1)f(x)$$

Notice now a discrete analog of Taylor's theorem is trivial to prove in that

$$f(x) \approx \sum_{i=0}^{\infty}\left[ \frac{Q_w^i[f(x)](a)}{i!} \prod_{j=0}^{i}\left[(x -j - a) \right] \right] $$

in the neighborhood of $a$.

We can basically then generate a taylor series for this difference equation:

$$Q_1[f(x)] = (x-1)f(x)$$

By noting in general

$$Q_1^n[f(x)] = nQ_1^{n-1}[f(x)] + (n-1)Q_1^{n-2}[f(x)]$$

If we center ourselves around $x = 0$ and $f(0) = 1$. I leave the details of solving the recursion out though i'll happily elaborate if ya'll want more detail.

All in all the resulting expression I get from this Taylor's Theorem Analog is:

$$\left(\frac{1}{0!}\right) + \left(\frac{1}{0!}- \frac{1}{1!}\right)x + \left(\frac{1}{0!}- \frac{1}{1!} + \frac{1}{2!}\right) x(x-1) + \left(\frac{1}{0!}- \frac{1}{1!} + \frac{1}{2!} -\frac{1}{3!} \right)x(x-1)(x-2) ... = x!$$

After simplifying a ton.

I'm hoping there's an easier way to show this.

Answer 1

I think that your formula is a particular case of the Newton interpolation formula: Let $f(n)$ a fonction on $\mathbb{N}=\{0,1,\cdots\}$, put $\displaystyle a_n=\sum_{k=0}^n(-1)^k \binom{n}{k}f(n-k)$, and $\displaystyle g(x)=\sum_{n\geq 0}a_n\binom{x}{n}$, then we have $g(m)=f(m)$ for all $m \in \mathbb{N}$. (Also, look at your formula: for $i=0$, we get $x$, not $1/(0!)=1$).

Answer 2

Is induction on $x$ acceptable? Because:

$\sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x+1-j)\right] \right] =\sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=-1}^{i}\left[ (x-j)\right] \right] =\sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] (x+1)\prod_{j=0}^{i}\left[ (x-j)\right] \right] =(x+1)x!=(x+1)!$

I agree that it is not helping understand where the formula comes from, but it does the job.

Answer 3

Here is a start. We write the product as

$$ \prod_{j=0}^{i}\left[ (x-j)\right] = \frac{x!}{\Gamma(x-i)}. $$

The sum $S$ becomes

$$ S = x!\sum_{i = 0}^{\infty}\sum_{j=0}^{i}\frac{(-1)^j}{j!} \frac{1}{\Gamma(x-i)}=x!\sum_{i = 0}^{x-1}\sum_{j=0}^{i}\frac{(-1)^j}{j!} \frac{1}{\Gamma(x-i)} $$

since the gamma function $\Gamma(x-i)$ will start having poles from $i=x$. Interchanging the order of the sums gives

$$ S = x!\sum_{j = 0}^{x-1}\frac{(-1)^j}{j!} \sum_{i=j}^{x-1}\frac{1}{\Gamma(x-i)} = x!.1. $$

You need to prove that

$$ \sum_{j = 0}^{x-1}\frac{(-1)^j}{j!} \sum_{i=j}^{x-1}\frac{1}{\Gamma(x-i)} =1 $$

to finish the problem.

Answer 4

\begin{align*} \sum_{i=0}^\infty \sum_{j=0}^i \frac{(-1)^j}{j!} \prod_{k=0}^i (x-k) &= \sum_{i=0}^{\color{red}{x-1}} \sum_{j=0}^i \frac{(-1)^j}{j!} \prod_{k=0}^i (x-k) \\ &= x! \sum_{i=0}^{x-1} \sum_{j=0}^i \frac{(-1)^j}{j!(x-i-1)!} \\ &= x! \sum_{i=0}^{x-1} \sum_{j=0}^{x-i-1} \frac{(-1)^j}{j!\,i!} &&\text{(reindex $i:=x-i-1$)} \\ &= x! \sum_{i=0}^{x-1} \sum_{j=i}^{x-1} \frac{(-1)^{j-i}}{(j-i)!\,i!} &&\text{(reindex $j:=j-i$)} \\ &= x! \sum_{i=0}^{x-1} \sum_{j=i}^{x-1} \frac{(-1)^{j-i}}{j!} \binom ji \\ &= x! \sum_{i=0}^{x-1} \sum_{j=\color{red}{0}}^{x-1} \frac{(-1)^{j-i}}{j!} \binom ji \\ &= x! \sum_{j=0}^{x-1} \frac{(-1)^j}{j!} \sum_{i=0}^{x-1} (-1)^i \binom ji \\ &= x! \sum_{j=0}^{x-1} \frac{(-1)^j}{j!} \sum_{i=0}^{\color{red}{j}} (-1)^i \binom ji \\ &= x! \sum_{j=0}^{x-1} \frac{(-1)^j}{j!} (1-1)^j \\ &= x! \frac{(-1)^0}{0!} \\ &= x! \end{align*} I've made use of the usual conventions that $\binom ji=0$ if $j<i$, and $0^0=1$.