## A Proof of Dobinski’s Formula for Bell Numbers

Dobinski’s formula entails the following infinite series expression for the nth Bell number $\varpi_n$:

$\displaystyle \varpi_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}.$

In this post we’ll work through a proof of Dobinski’s formula.  We’ll need four formulas:

1. The Maclaurin series for $e^x$: $\displaystyle e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$.
2. The formula for converting normal powers to falling factorial powers: $\displaystyle x^n = \sum_{k=0}^n \left\{ n \atop k \right\} x^{\underline{k}},$ where $\left\{ n \atop k \right\}$ is a Stirling number of the second kind.
3. The formula relating Bell numbers and Stirling numbers of the second kind: $\displaystyle \varpi_n = \sum_{k=0}^n \left\{ n \atop k \right\}$.  (This follows directly from the combinatorial definitions of the Bell numbers and the Stirling numbers of the second kind.)
4. The representation of falling factorial powers as factorials: $\displaystyle k^{\underline{m}} = \frac{k!}{(k-m)!}$, valid when $k \geq m$ and $k, m \in \mathbb{N}$.

Here we go… Starting with the infinite series expression $\displaystyle \sum_{k=0}^{\infty} \frac{k^n}{k!},$ convert to falling factorial powers to get

$\displaystyle \sum_{k=0}^{\infty} \frac{k^n}{k!} = \sum_{k=0}^{\infty} \frac{1}{k!} \sum_{j=0}^n \left\{n \atop j \right\} k^{\underline{j}} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{k=0}^{\infty} \frac{k^{\underline{j}}}{k!} = \sum_{j=0}^n \left\{n \atop j \right\} \sum_{k=j}^{\infty} \frac{k^{\underline{j}}}{k!} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{k=j}^{\infty} \frac{1}{(k-j)!} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{i=0}^{\infty} \frac{1}{i!} = \sum_{j=0}^n \left\{ n \atop j \right\} e.$

Thus $\displaystyle \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!} = \frac{1}{e} \sum_{j=0}^n \left\{ n \atop j \right\} e = \varpi_n$.

(I made a similar argument in this Math.SE question.)