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?

  • $\begingroup$ Can you please define the "falling factorial"? $\endgroup$ – Gregory Grant May 7 '15 at 17:12
  • $\begingroup$ $n^{\underline{k}} = \frac{n!}{(n-k)!}$ $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.