Vtgyjfy

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 {nchoose i}{kchoose {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^isum_{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}^rbinom{n}{i}binom{m}{r-i}x^r
end{align}
Then compare the coefficient

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 $0le 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 $displaystylesum_{i=0}^r binom{n}{i}binom{m}{r-i}$ .

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

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 $0leq r leq min {r,n}$. However, if you define $binom {n} {i}$ to be $0$ when $i >n$ then the formula is correct.