# Proving $\binom{n + m}{r} = \sum_{i = 0}^{r} \binom{n}{i}\binom{m}{r - i}$

To prove $$\binom{n + m}{r} = \sum_{i = 0}^{r} \binom{n}{i}\binom{m}{r - i},$$

I demonstrated that the equality is true for any $$n,$$ for $$m = 0, 1,$$ and for any $$r < n + m$$ simply by fixing $$n$$ and $$r$$ and inserting $$0,1$$ for $$m.$$ Then, I proceed to induct on $$m$$ (and on $$m$$ only).

I am not perfectly confident in my self, however, for I see two placeholders, $$n$$ and $$m.$$ Is this a case where double induction is needed (first on $$m$$ and then on $$n$$)?

Whether or not this proof requires double induction, may someone explain when double induction is needed?

Consider any fixed $$n, r \geq 0$$ and the following two cases (I know that only one case is needed to complete this inductive proof).

CASE 1

\begin{align} \binom{n + 0}{r} &= \sum_{i = 0}^{r} \binom{n}{i}\binom{0}{r - i} \\ &= \binom{n}{0}\binom{0}{r} + \binom{n}{1}\binom{0}{r-1} + \cdots + \binom{n}{r}\binom{0}{0} \\ &= 0 + 0 + \cdots + \binom{n}{r} \\ &= \binom{n}{r} \end{align}

CASE 2

\begin{align} \binom{n + 1}{r} &= \sum_{i = 0}^{r} \binom{n}{i}\binom{1}{r - i} \\ &= \binom{n}{0}\binom{0}{r} + \binom{n}{1}\binom{0}{r-1} + \cdots + \binom{n}{r-1}\binom{1}{r - (r-1)} + \binom{n}{r}\binom{1}{r - r} \\ &= 0 + 0 + \cdots + \binom{n}{r-1} + \binom{n}{r} \\ &= \binom{n}{r-1} + \binom{n}{r} \end{align}

INDUCTION

Suppose it is true for $$m \leq k.$$ Now, consider $$\binom{n + (k + 1)}{r}.$$ It follows from Pascal's Identity that

$$\binom{n + (k+1)}{r} = \binom{n + k}{r} + \binom{n + k}{r-1}$$

And,

\begin{align} \binom{n + k}{r} + \binom{n + k}{r-1} &= \sum_{i = 0}^{r} \binom{n}{i}\binom{k}{r - i} + \sum_{i = 0}^{r-1} \binom{n}{i}\binom{k}{r - 1 - i} \\ &= \binom{n}{r} + \sum_{i = 0}^{r-1} \binom{n}{i}\binom{k}{r - i} + \sum_{i = 0}^{r-1} \binom{n}{i}\binom{k}{r - 1 - i} \\ &= \binom{n}{r} + \sum_{i = 0}^{r-1} \binom{n}{i}\bigg[\binom{k}{r - i} + \binom{k}{r - 1 - i}\bigg] \\ &= \binom{n}{r} + \sum_{i = 0}^{r-1} \binom{n}{i}\binom{k+1}{r-i} \\ &= \sum_{i = 0}^{r} \binom{n}{i}\binom{k+1}{r-i} \end{align}

Hence, the equality holds for $$m = k + 1.$$ Given that the equality holds for $$m = 0, 1,$$ and that if equality holds for $$m = k,$$ it then holds for $$m = k + 1,$$ it follows that the equality holds $$\forall m \in \mathbb{N}.$$

For a short reply, your induction proof has tiny problem, in that $$r$$ can take value $$n+k$$ for the $$m = k+1$$ induction step. So when you use induction hypothesis to get $${{n+k}\choose{r}} = \sum_{i=1}^r {n\choose i}{k\choose {r-i}}$$, you can actually use it only for $$r. This is not big problem though as the $$r = n+k$$ case is trivial.

For the double-induction, I don't think it's necessary here. The reason is that you are actually fixing an arbitrary $$n$$ first, and then do induction proof. So the induction proof is within the context of the fixed $$n$$.

Note that$$(x+1)^{n+m}=(x+1)^n(x+1)^m$$ Then by binomial theorem and collecting terms \begin{align} \sum_{r=0}^{n+m}\binom{n+m}{r}x^r &= \sum_{i=0}^{n}\binom{n}{i}x^i\sum_{j=0}^{m}\binom{m}{j}x^j \\&= \sum_{r=0}^{n+m}\sum_{i+j=r}\binom{n}{i}\binom{m}{j}x^r \\ &= \sum_{r=0}^{n+m}\sum_{i=0}^r\binom{n}{i}\binom{m}{r-i}x^r \end{align} Then compare the coefficient

• Hey, Dragunity. Thank you for your response. I appreciate the alternative look. However, my question was with regards double induction was needed. And, a more general clarification as to when double induction should be used. Maybe you have some input on that? – Rafael Vergnaud Jan 21 at 19:46
• Regardless, thanks for your input :) – Rafael Vergnaud Jan 21 at 19:46
• No need to use double induction as the n is arbitrarily when you use induction on m. – DragunityMAX Jan 23 at 9:34
• I seldom see the usage of double induction so I not quite sure about it. You use induction as you can derive case n+1 from cases <= n. Similarly, you use double induction when you can derive case (n+1,m) and (n,m+1) from cases (<=n, <=m). But double induction can always reduce to normal induction by defining an appropriate sequence. @RafaelVergnaud – DragunityMAX Jan 23 at 9:43

You can think of a combinatoric proof as follows.

Suppose we have $$n$$ men and $$m$$ women, and we wish to form a committee of $$r$$ people. We can count in two different ways.

Case 1 $$\binom{n+m}{r}$$ is the number of r-subsets of a set with n+m elements.

Case 2 First we pick $$i$$ males. That leaves $$r-i$$ female to choose. So given $$0\le i \le r$$ We have $$\binom{n}{i}\binom{m}{r-i}$$ such committees. If we let $$i$$ range, we add up all these committees, so we get $$\displaystyle\sum_{i=0}^r \binom{n}{i}\binom{m}{r-i}$$ .

Since both cases count the same number, they must be equal.

• Hi, Joel. Thanks for your response. I'm aware of the combinatorial explanation for the equality. I was interested in also proving the identity analytically. I was not sure, however, whether single induction (on $m$) was sufficient! Regardless, thanks :) – Rafael Vergnaud Jan 21 at 0:21

I think the formula is wrong. If you have $$n$$ white balls and $$m$$ red balls then, to choose $$r$$ balls from then you have to choose $$i$$ white balls and $$r-i$$ red balls for some $$i$$ between $$0$$ and $$\min \{r,n\}$$. Hence the sum should be over $$0\leq r \leq \min \{r,n\}$$. However, if you define $$\binom {n} {i}$$ to be $$0$$ when $$i >n$$ then the formula is correct.

• Hi, Kavi. Thank you for your response. :) I suppose the identity does rely on the convention that $\binom{n}{I} = 0$ when $I > n.$ The identity comes straight out of a textbook, namely Sheldon Ross's A first Course in Probability. (Not that this means the identity is necessarily correct). – Rafael Vergnaud Jan 21 at 0:11