Proving the equation using binomial theorem

Question

I want to prove this theorem using Binomial theorem and I've got trouble in understanding 3rd step if anyone knows why please explain :) Prove that sum:

$\sum_{r=0}^{k}\binom{m}{r}\binom{n}{k-r}=\binom{m+n}{k}$

1st step:
$(1+y)^{m+n}=(1+y)^m(1+y)^n$

2nd step: we use the binomial theorem formula and evaluate that sum $\sum_{m+n}^{r=0}\binom{m+n}{r}y^r=\sum_{r=0}^{m}\binom{m}{r}y^r \sum_{r=0}^{n}\binom{n}{r}y^r$

3step: equating the coefficient of $y^k$

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

Why and how is the 3rd step allowed? Thank you

Answer 1

If $c_0+c_1y+\cdots +c_{n+m}y^{n+m}=d_0+d_1y+\cdots +d_{n+m}y^{n+m}$ for all $y$ then $c_i=d_i$ for all $i$. This is a basic fact about polynomials (and comes from the fact that a non-zero polynomial has only finitely many zeros). This result allows you to equate the coefficients of like powers of $y$.

Answer 2

In the 3rd step, $$\sum_{k=0}^{m+n} {m+n\choose k} y^k = \sum_{i=0}^m {m\choose i} y^i\sum_{i=0}^n{n\choose j} y^j =\sum_{k=0}^{m+n} \sum_{i,j\atop i+j=k}{m\choose i}{n\choose j} y^k.$$ This gives the desired equation.

Answer 3

Let $a_i\in\mathbb R$ denote a constant for $i=0,1,\dots,n$.

The function $\mathbb R\to\mathbb R$ prescribed by $x\mapsto\sum_{i=0}^na_ix^i$ is the same as the function $\mathbb R\to\mathbb R$ prescribed by $x\mapsto 0$ if and only if $a_i=0$ for every $i\in\{0,1,\dots,n\}$.

Sufficiency is obvious. Necessity is a consequence of the fact that the first function has at most $n$ roots if $a_i\neq0$ for some $i\in\{0,1,\dots,n\}$.

This can be applied by proving that two polynomial functions $p_1,p_2$ are the same (or equivalently $p_1-p_2$ is the zero function) if and only if they have the same coefficients.

Answer 4

By the equation of 2nd step,

Left: $$\binom{m+n}{0}y^{0}+\binom{m+n}{1}y^{1}+\cdots+\binom{m+n}{m+n-1}y^{m+n-1}+\binom{m+n}{m+n}y^{m+n}$$

The coefficient of $y^{k}$ is $\binom{m+n}{k}$

Right: $$(\binom{m}{0}y^{0}+\cdots+\binom{m}{m}y^{m})(\binom{n}{0}y^{0}+\cdots+\binom{n}{n}y^{n}) $$

The term $y^{k}$ come from $$\binom{m}{0}y^{0}\binom{n}{k}y^{k}+\binom{m}{1}y^{1}\binom{n}{k-1}y^{k-1}+ \cdots +\binom{m}{k-1}y^{k-1}\binom{n}{1}y^{1}+\binom{m}{k}y^{k}\binom{n}{0}y^{0}$$

So the coefficient of $y^{k}$ is $\binom{m}{0}\binom{n}{k} + \binom{m}{1}\binom{n}{k-1}+ \cdots +\binom{m}{k-1}\binom{n}{1}+\binom{m}{k}\binom{n}{0}$

By the equality of the equation of 2nd step, the coefficient of $y^{k}$ of left and right might be the same, so $$\binom{m+n}{k} = \binom{m}{0}\binom{n}{k} + \binom{m}{1}\binom{n}{k-1}+ \cdots +\binom{m}{k-1}\binom{n}{1}+\binom{m}{k}\binom{n}{0}$$