If $f(n, k)$ is the number of ways to divide the set $\{1,2, \ldots, n\}$ into $k$ nonempty subsets and $m$ is a positive integer, find a formula for $\sum_{k=1}^{n} f(n, k) m(m-1)(m-$ 2) $\cdots(m-k+1)$.
We claim that the sum is equal to $m^{n}$. We note that $m^{n}$ counts the number of ways to color $n$ objects each with one of $m$ different colors, so it suffices to show that the left side counts the same thing. We can consider cases based on how many different colors get used. If $k$ colors are used, then there are $f(n, k)$ ways to choose how to split the objects into subsets based on color, then $m$ ways to choose the color of the first subset, $m-1$ ways to colors the second one, and so on. Summing over $k$ from 1 to $n$ gives the desired sum.

(The numbers $f(n, k)$ are known as Stirling numbers of the second kind, and are usually denoted $S(n, k)$ or $\left\{\begin{array}{l}n \\ k\end{array}\right\}$.)