Factorial as Sum of Series of Subfactorial by Falling Factorial over Factorial/Proof

From ProofWiki
Jump to navigation Jump to search

Theorem

\(\displaystyle n!\) \(=\) \(\displaystyle \sum_{k \mathop \ge 0} \dfrac { {!k} \, n^{\underline k} } {k!}\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac { !0 \times n^{\underline 0} } {0!} + \dfrac { {!1} \times n^{\underline 1} } {1!} + \dfrac { {!2} \times n^{\underline 2} } {2!} + \dfrac { {!3} \times n^{\underline 3} } {3!} + \cdots\)
\(\displaystyle \) \(=\) \(\displaystyle 1 + \left({1 - \dfrac 1 {1 !} }\right) n + \left({1 - \dfrac 1 {1 !} + \dfrac 1 {2 !} }\right) n \left({n - 1}\right) + \left({1 - \dfrac 1 {1 !} + \dfrac 1 {2 !} - \dfrac 1 {3 !} }\right) n \left({n - 1}\right) \left({n - 2}\right) + \cdots\)


Proof

Let $n$ be a non-negative integer.

We assume a solution of the form:

$(1): \quad n! = a_0 + a_1 n + a_2 n \left({n - 1}\right) + a_3 n \left({n - 1}\right) \left({n - 2}\right) + \cdots$


We can express $(1)$ using binomial coefficients:

$(2): \quad n! = \displaystyle \sum_k \dbinom n k k! a_k$


Then:

\(\displaystyle \sum_n n! \binom m n \left({-1}\right)^{n - k}\) \(=\) \(\displaystyle \sum_n \left({\sum_k \binom n k k! \, a_k}\right) \binom m n \left({-1}\right)^{n - k}\) substituting for $n!$ from $(2)$
\(\displaystyle \) \(=\) \(\displaystyle \sum_k k! \, a_k \sum_n \binom n k \binom m n \left({-1}\right)^{m - n}\) changing order of summation
\(\displaystyle \) \(=\) \(\displaystyle \sum_k k! \, a_k \delta_{k m}\) Corollary to Sum over $k$ of $\dbinom r k \dbinom {s + k} n \left({-1}\right)^{r - k}$
\(\displaystyle \) \(=\) \(\displaystyle m! \, a_m\) as the $m$th term is the only one left standing
\(\displaystyle \leadsto \ \ \) \(\displaystyle a_m\) \(=\) \(\displaystyle \sum_{n \mathop \ge 0} \left({-1}\right)^{m - n} \dfrac {n!} {m!} \binom m n\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{n \mathop = 0}^m \left({-1}\right)^{m - n} \dfrac {n!} {m!} \dfrac {m!} {n! \, \left({m - n}\right)!}\) Definition of Binomial Coefficient
\(\displaystyle \) \(=\) \(\displaystyle \sum_{n \mathop = 0}^m \frac {\left({-1}\right)^{m - n} } {\left({m - n}\right)!}\) simplifying
\(\displaystyle \) \(=\) \(\displaystyle \sum_{n \mathop = 0}^m \frac {\left({-1}\right)^n} {n!}\) Permutation of Indices of Summation

$\blacksquare$


Sources