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.
 A: $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.
A: As a source for my answer I use the following book: Graham,Knuth,Patashnik.Concrete mathematics
They define an operator $\Delta f=f(x+1)-f(x)$ and an inverse operator $\Delta^{-1}f=\sum f(x)\delta x$, where $x \in \mathbb Z$ (this operator is called indefinite sum).
They also define "definite sum": 
If $g(x)=\Delta f(x)$, then $\sum_a^bg(x)\delta x = f(x)\Bigr|_a^b=f(b)-f(a)$
Then they show that $\sum_a^b g(x)\delta x=\sum\limits_{k=0}^{b-1}g(k)$ when $b>a, b \in \mathbb Z, a \in \mathbb Z$
So you should just prove that $\Delta x^\underline{m}=mx^\underline{m-1}$
And by the way $m$ can be nonpositive.
