# Combinatorial Proof of falling factorial and binomial theorem

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?

• Can you please define the "falling factorial"? – Gregory Grant May 7 '15 at 17:12
• $n^{\underline{k}} = \frac{n!}{(n-k)!}$ – grapher May 7 '15 at 17:17

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

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

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*}

This also follows from Vandermonde's identity, i.e. $$\binom{n+m}{k}=\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}$$ which can be proven using a commitee like argument, namely two ways of choosing a group of $k$ people from $n$ men and $m$ women. Multiply both sides by $k!$ to get that $$(n+m)^{\underline{k}} =\sum_{i=0}^k\binom{k}{i}n^{\underline i} m^{\underline {k-i}}$$ as desired.