Combinatorial Proof of falling factorial and binomial theorem

Question

For $n,m,k \in \mathbb{N}$, prove the equality $$(n+m)^{\underline{k}}=\sum^{k}_{i=0}\binom ki \cdot n^{\underline{k-i}} \cdot m^{\underline{i}}$$ Here, $x^{\underline{j}}$ denotes a falling factorial, defined by $x^{\underline{j}} = \dfrac{x!}{\left(x-j\right)!} = x\left(x-1\right)\cdots\left(x-j+1\right)$.

I can prove the binomial theorem for itself combinatorically and also the falling factorial version of it, but combined I hit a wall. Any suggestions?

Answer 1

How many ways can you pick $k$ balls from a set of $n$ different red balls and $m$ green different balls?

Answer

$$(n+m)^{\underline k}$$

But you can count them another way. First suppose that the $k$ balls are red, then $k-1$ are red and $1$ is green, etc.

This gives

$$\sum_{j=0}^k\binom kj n^{\underline j} m^{\underline {k-j}}$$

Answer 2

I much prefer the combinatorial argument, but it’s useful to be able to manipulate summations and falling factorials, so here for the record is the induction step of the proof by induction on $k$.

$$\begin{align*} \sum_{i=0}^{k+1}\binom{k+1}in^{\underline{k+1-i}}m^{\underline i}&=\sum_{i=0}^{k+1}\left(\binom{k}i+\binom{k}{i-1}\right)n^{\underline{k+1-i}}m^{\underline i}\\ &=\sum_{i=0}^k\binom{k}in^{\underline{k+1-i}}m^{\underline i}+\sum_{i=0}^k\binom{k}in^{\underline{k-i}}m^{\underline{i+1}}\\ &=\sum_{i=0}^k\binom{k}i\left(n^{\underline{k+1-i}}m^{\underline i}+n^{\underline{k-i}}m^{\underline{i+1}}\right)\\ &=\sum_{i=0}^k\binom{k}in^{\underline{k-i}}m^{\underline i}\big((n-k+i)+(m-i)\big)\\ &=\sum_{i=0}^k\binom{k}in^{\underline{k-i}}m^{\underline i}(n-k+m)\\ &=(n+m-k)(n+m)^{\underline k}\\ &=(n+m)^{\underline{k+1}}\;. \end{align*}$$