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


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


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


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


\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<n+k$. 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

  • $\begingroup$ 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? $\endgroup$ – Rafael Vergnaud Jan 21 at 19:46
  • $\begingroup$ Regardless, thanks for your input :) $\endgroup$ – Rafael Vergnaud Jan 21 at 19:46
  • $\begingroup$ No need to use double induction as the n is arbitrarily when you use induction on m. $\endgroup$ – DragunityMAX Jan 23 at 9:34
  • 1
    $\begingroup$ 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 $\endgroup$ – 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.

  • $\begingroup$ 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 :) $\endgroup$ – 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.

  • $\begingroup$ 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). $\endgroup$ – Rafael Vergnaud Jan 21 at 0:11

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.