1
$\begingroup$

As the title says, I was requested to prove

$\binom{m+n}{r}=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + ... +\binom{m}{r}\binom{n}{0}$

I was requested to do this using the following identity:

$(1+x)^n(1+x)^m=(1+x)^{n+m}$

Whenever I say identity I shall be meaning this identity; when a talk about the equation I shall be meaning the equation I was requested to prove.

I think I have found the proof, but I'm not sure if it's right (I'm fairly new to this subject), so I would like someone with more experience to help me deciding on this, and point my errors if any.

Firstly, I expand the binomials on the left-hand side of the identity. They are, according to the binomial theorem,

$\sum_{r=0}^{n}\binom{n}{r}1^{n-r}x^{r} = \binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n}x^n$

and

$\sum_{r=0}^m \binom{m}{r}1^{m-r}x^r=\binom{m}{0}+\binom{m}{1}x+\binom{m}{2}x^2+...+\binom{m}{m}x^m$

Now that we expanded the factors of the left-hand side of our identity, we shall inspect the right-hand side of the equation and notice that it is the summation of the products of the expanded factors that are coefficient of $x^n$. For example, the first term of the right-hand side of the equation is $\binom{m}{0}\binom{n}{r}$. When we multiply $(1+x)^n(1+x)^m$, one of the coefficients of $x^n$ on the result is in deed the first element of the first factor multiplied by the last element of the second factor , $\binom{m}{0}\binom{n}{n}x^n$.

So now we know that the right-hand side of the equation is the coefficients of $x^n$ on the multiplication of $(1+x)^n(1+x)^m$. Because we know our identity is true, if we could prove that the $x^n$ coefficients of the right-hand of our identity is equal to the left-hand side of our equation, we would have proved our equation, since this would show both sides of our equation are just the $x^n$ coefficient of $(1+x)^n(1+x)^m$.

This can be shown expanding the right-hand side of our identity,

$\sum_{r=0}^{n+m}\binom{n+m}{r}1^{n+m-r}x^r=\binom{n+m}{0}+\binom{n+m}{1}+...+\binom{n+m}{n}x^n+...+\binom{n+m}{n+m}x^{n+r}$

As we can see, $\binom{n+m}{n}$ is the coefficient of $x^n$ too (just written differently). We know this is right because our identity is true. Let's call the $x^n$ coefficient $C$. If $C=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + ... +\binom{m}{r}\binom{n}{0}$ and $C=\binom{m+n}{r}$, then we proved our equation:

$\binom{m+n}{r}=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + ... +\binom{m}{r}\binom{n}{0}$

Is this proof right?

$\endgroup$
1
$\begingroup$

It sounds right, but I would write it like$$\sum_{k=0}^m\sum_{l=0}^n\binom{m}{k}\binom{n}{l}x^{k+l}=(1+x)^m(1+x)^n=(1+x)^{m+n}=\sum_{r=0}^{m+n}\binom{m+n}{r}x^r$$so that$$\binom{m+n}{r}x^r=\sum_{i=0}^r\binom{m}{i}\binom{n}{r-i}x^r.$$Then letting $x=1$ yields the desired expression.

| cite | improve this answer | |
$\endgroup$

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.