Alternative proofs: I have worked about a result and want to know if there are better ways of proving the following:
$$N^M - (N-1)^M$$
$$=\binom{N}{1}(N-1)^{M-1} + \binom{N}{2} (N-1)^{M-2} + \binom{N}{3} (N-1)^{M-3} + \cdots
+\binom{N}{M}(N-1)^{M-M}.$$
 A: This is the expansion of $N^M=((N-1)+1)^M$, if you adjust the $(N,C,k)$ to $(M,C,k)$
A: We give a combinatorial interpretation, with the $\binom{N}{k}$ replaced by the correct $\binom{M}{k}$.
We have $N$ kids, one of whom is George, and $M$ distinct presents. We want to count, in two different ways,  the number of ways to give out the presents, with George getting at least $1$ present.
Way $1$: There are $N^M$ ways to distribute the presents. There are $(N-1)^M$ ways to distribute the presents among the $N-1$ non-Georges. So there are $N^M-(N-1)^M$ ways to not shut George out.
Way $2$: George may get anywhere from $1$ to $M$ presents. We count the number of ways to distribute the presents so Geoge gets $k$. The $k$ presents George gets can be chosen in $\binom{M}{k}$ ways. For each such way, the remaining $M-k$ presents can be distributed among the remaining kids in $(N-1)^{M-k}$ ways. So there are $\binom{M}{k}(N-1)^{M-k}$ ways to distribute the presents so George gets $k$. Now sum from $k=1$ to $k=M$. 
