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 Answer 1

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .