Alternative proofs:

Question

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}.$$

Answer 1

This is the expansion of $N^M=((N-1)+1)^M$, if you adjust the $(N,C,k)$ to $(M,C,k)$

Answer 2

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$.