Can't prove this algebraically $\sum\limits_{i = 0}^n { n \choose i } \, !i = n! $

Question

I'm stumped as to how to prove this formula $$ \sum\limits_{i = 0}^n { n \choose i } \, !i = n! \tag{1} $$ using only the "algebraic" properties of the binomial coefficient $ n \choose i $ and the subfactorial operator $!i$ (the number of derangements of $i$ elements.)

There's an easy counting argument that proves the formula. (Each term in the sum is the number of permutations of $n$ elements that leave $(n-i)$ elements fixed.) But shouldn't we also be able to prove it algebraically using only the properties of the operators?

Here are the three pertinent properties of $!i$ that I found at https://en.wikipedia.org/wiki/Derangement $$ !i = (i-1)(\, !(i-1) \,+\, !(i-2) ) \tag{2}$$ $$ !i = i! \, \sum\limits_{j = 0}^i {\frac{(-1)^j}{j!} } \tag{3}$$ $$ !i = i \,\cdot\, !(i-1)+(-1)^i \tag{4}$$

However, it seems like these properties of $!i$ are not enough to prove $(1)$. Help!

Is it possible to have a formula that can only be proved with a "counting argument" and not "algebraically"?

Answer 1

\begin{align} \sum_{i=0}^n \binom{n}{i} !i &=\sum_{i=0}^n \binom{n}{i}i!\sum_{j=0}^i \frac{(-1)^j}{j!}\\ &=\sum_{j=0}^n \frac{(-1)^j}{j!}\sum_{i=j}^n\frac{n!}{(n-i)!}\\ &=n!\sum_{0\leq j\leq i\leq n} \frac{(-1)^j}{j!(n-i)!}. \end{align}

Fixing $k=n-i+j$, we sum over $0\leq j\leq n+j-k\leq n$, which is simply the region $0\leq j\leq k$ for $0\leq k\leq n$:

\begin{align} \sum_{i=0}^n \binom{n}{i} !i &=n!\sum_{k=0}^n\sum_{j=0}^k \frac{(-1)^j}{j!(k-j)!}\\ &=n!\sum_{k=0}^n\frac{1}{k!}\sum_{j=0}^k (-1)^j\binom{k}{j}. \end{align}

For $k\geq 1$, the inside sum is the expansion of $(1-1)^k$ by the binomial theorem, so it equals $0$ if $k\neq 0$. So, the only term left is $k=0$, for which the inside sum is just $1$, and thus the full sum is simply $n!$.

Answer 2

Hint: Let $S_n=\sum\limits_{i = 0}^n { n \choose i } \, !i$. It is enough to prove that $S_0=1$ and $S_n=nS_{n-1}$ for $n\ge1$.

Answer 3

Brilliant! Thank you everyone. I've got it now. Yes, I forgot to consider the iterative property of n! Here are the details...

We'll use property (4) in the original post. And we'll use these two properties of the binomial coefficient. $$ \sum_{i=0}^n{(-1)^i {n\choose i}}=0 \,\,\,\,, n>0\tag{5} $$ $$ i{n \choose i}=n {n-1 \choose i-1} \,\,\,\,, n>0, i>0\tag{6} $$ Here's the proof.

Let $S_n=\sum_{i=0}^n{n\choose i}!i$. We'll show $S_0=1$ and $S_n=nS_{n-1}$ for all $n>0$.

(1) $S_0={0 \choose 0} !0 = 1$

(2) Let $n>0$. Then $$ \begin{aligned} S_n &=\sum_{i=0}^n{n\choose i}!i \\ &=1+ \sum_{i=1}^n{n\choose i}!i \\ &= 1+\sum_{i=1}^n{n\choose i} (i \, !(i-1)+(-1)^i) \\ &= 1+\sum_{i=1}^n{n\choose i} i \, !(i-1)+\sum_{i=1}^n{n\choose i} (-1)^i \\ &= \sum_{i=1}^n{n\choose i} i \, !(i-1)+\sum_{i=0}^n{n\choose i} (-1)^i \\ &= \sum_{i=1}^n{n\choose i} i \, !(i-1) \\ &= \sum_{i=1}^n n {n-1 \choose i-1} \, !(i-1) \\ &= n \sum_{i=0}^{n-1} {n-1 \choose i} \, !i \\ &= n S_{n-1} &\square\\ \end{aligned} $$