Falling Factorial Identity I would like to prove the following identity, preferably using a combinatorial argument 
$$\sum_{k=0}^n k^{\underline{m}} = \frac{(n+1)^{\underline{m+1}}}{m+1}$$
I'm assuming $m \ge 0$, although the problem doesn't mention anything. I'm not entirely sure where to begin. The thing I have most trouble with are the terms in the sum such as $0^\underline{m}$. To me terms such as these (where $m \ge k$) dont have an obvious combinatorial interpretation. 
A solution, any insight as to how to begin and/or a way of interpreting an expression like $0^\underline{m}$ as counting something would be much appreciated.

$k^{\underline m}$ is the number of permutations of $m$ distinct objects chosen from a set of $k$ objects; this is of course $0$ if $m>k$. 
The lefthand side is the number of ordered pairs $\langle\sigma,k\rangle$ such that $0\le k\le n$ and $\sigma$ is a sequence of $m$ distinct elements of the $k$-element set $\{0,1,\ldots,k-1\}$. Now consider the righthand side.
There are $(n+1)^{\underline{m+1}}$ ways to choose a sequence of $m+1$ elements of the set $\{0,1,\ldots,n\}$. Suppose that the largest term of the sequence is $k$; removing that $k$ leaves a sequence of $m$ elements of the $k$-element set $\{0,1,\ldots,k-1\}$. Since the $k$ can be any of the $m+1$ terms of the original sequence, each $m$-sequence from $\{0,1,\ldots,k-1\}$ arises in this way from $m+1$ different $(m+1)$-sequences from $\{0,1,\ldots,n\}$. There are $k^{\underline m}$ $m$-sequences from $\{0,1,\ldots,k-1\}$, so there are $(m+1)k^{\underline m}$ $(m+1)$-sequences from $\{0,1,\ldots,n\}$ having $k$ as largest term. Thus,
$$(n+1)^{\underline{m+1}}=(m+1)\sum_{k=0}^nk^{\underline m}\;,$$
and the result follows.
