Factorial identity $n!=1+(1-1/1!)n+(1-1/1!+1/2!)n(n-1)+\cdots$

Question

Show that $\displaystyle{n!=1+\left(1-\frac1{1!}\right)n+\left(1-\frac1{1!}+\frac1{2!}\right)n(n-1)+\cdots}$. I can't figure out how this can be solved. I tried to use the binomial theorem but I couldn't prove it. Any help will be greatly appreciated.

Answer 1

Assuming the sum is supposed to terminate after $n$ terms, your sum is:

$$ \frac{n!}{n!} \sum_{k=1}^{n+1} \sum_{m=1}^k \frac{(-1)^{m-1}}{(m-1)!}\prod_{r=0}^{k-2} (n-r) $$

$$ =n!\sum_{k=1}^{n+1} \sum_{m=1}^k \frac{(-1)^{m-1}}{(m-1)!} \frac{\prod_{r=0}^{k-2} (n-r)}{n!} $$

$$ =n!\sum_{k=1}^{n+1} \sum_{m=1}^k \frac{(-1)^{m-1}}{(m-1)!(n+1-k)!} $$

$$ =n!\sum_{k=0}^{n} \sum_{m=0}^{k} \frac{(-1)^{m}}{m!(n-k)!} $$

$$ =n!\sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{m=0}^{k} \frac{(-1)^{m}}{m!} $$

$$ =\frac{1}{e}\sum_{k=0}^{n} \binom{n}{k}{\Gamma(k+1,-1)} $$ But I'm already just quoting the incomplete Gamma function which is essentially just rewriting the sum, I can't show this is $n!$.

Answer 2

If you divide by $n!$ then the requested identity is $$1=\sum_{k=0}^n\frac1{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!},$$ perhaps better written using the Iverson bracket as $$1=\sum_{j,k}\frac{(-1)^j}{j!k!}\bigl[j\ge0,k\ge0,j+k\le n\bigr].$$ (The bracket takes the value $1$ if the statement inside holds, and $0$ otherwise.)

Notice that $$\sum_{j,k}\frac{(-1)^j}{j!k!}\bigl[j\ge0,k\ge0,j+k=m\bigr] =\begin{cases}\dfrac{(1-1)^m}{m!}=0&m\ge1,\\1&m=0\end{cases}$$ Now sum this over $m\in\{0,1,\ldots,n\}$ to get the desired result.

Answer 3

Here is a combinatorial argument. Rewrite the sum like this $$0!\times 1 \color{#F00}{+} 1! (1-1/1!) n/1! \color{#F00}{+} 2! (1-1/1!+1/2!) n(n-1)/2! \\\color{#F00}{+} 3! (1-1/1!+1/2!-1/3!) n(n-1)(n-2)/3!+\ldots$$ Two observations: first the term $$q! \times (1-1/1!+1/2!-1/3!+\cdots\pm 1/q!)$$ counts derangements on permutations of $q$ elements and second the term $n(n-1)\cdots(n-q)/q!$ is ${n\choose q} = {n\choose n-q}$ says to choose $n-q$ elements from $n$ elements.

Therefore the sum is a classification of the set of permutations by the number of fixed points: choose $n-q$ fixed points and combine with a derangement on $q$ elements. There are $n!$ permutations however. Done.