Sum of the product of two combinations

Could anyone explain how this statement is true? You may notice that this statement is part of the process of adding two independent binomial r.v.'s.

$$ \ \sum_{x=0}^\infty{n \choose x}{m \choose w-x} ={n+m \choose w}\ $$

Solution 1:

As Bhaskar Vashishth answered, the equality can be proven by showing that both sides correspond to different methods of counting the same thing.

${n+m\choose w}$ counts all the ways to select $w$ items from $n+m$ distinct items.

${n\choose x}{m\choose w-x}$ counts all the ways to select $x$ items from $n$ distinct items, and $w-x$ items from $m$. If we sum this over all possible $x$ we have counted all the ways to select $w$ items from $m+n$ distinct items.

The two methods of counting are equivalent, therefore the equality is proven.

This technique is called a combinatorial proof. It is an elegant way of showing why such an equality holds using natural language to give an intuitive explanation.

Solution 2:

Suppose you have $n$ red balls and $m$ blue balls in an urn and you have to choose $w$ balls out of the urn. So R.H.S. must be clear. For L.H.S. see, if $w$ balls are picked either all will be blue or $1$ will be red and rest $w-1$ blue, or $2$ red and $w-2$ blue..... and so on summing all these possibilities you get all ways of selected $w$ balls from $n$ red balls and $m$ blue balls.

Just counting in two different ways.(and yes this is a proof, will also work in any exam)