Help proving an identity by induction on two variables I'm trying to prove by induction the following:
$$\displaystyle \binom{a}{0}\binom{b}{n}+\binom{a}{1}\binom{b}{n-1}+...+\binom{a}{n}\binom{b}{0}=\binom{a+b}{n}$$.
As I didn't know how to prove by induction on two variables, I'm following this other question (which I think it was very helpful), however, I'm stuck on the second step:
$$\forall x,y. P(x+1,y) \Rightarrow P(x,y+1)$$ which in this case, it means I have to prove:
$$\displaystyle \binom{a}{0}\binom{b+1}{n}+\binom{a}{1}\binom{b+1}{n-1}+...+\binom{a}{n}\binom{b+1}{0}=\binom{a+b+1}{n}$$
(by the way, I switched the variables order so I'm using $P(b,a)$
Maybe ironically, I tried to prove that by induction (this time on a single variable), but I don't know to proceed about it.
Any help?
Regards
 A: We write out (ugh!) an induction proof. The combinatorial (generating function) proof of Didier Piau, and the combinatorial argument of one of my comments, are far better.  The base case is obvious, at least if we use the convention that $\binom{u}{v}=0$ if $u<v$. So assume the result holds for $a=x$, $b=y$. We show it holds for $a=x+1$, $b=y$.
In the proof, we use the identity 
$$\binom{x+1}{k}=\binom{x}{k}+\binom{x}{k-1}.\qquad\qquad(\ast).$$ 
This has an easy combinatorial proof. You can also verify it by using the ordinary formula for the binomial coefficients in terms of factorials, and doing a bit of algebra. 
So look at 
$$\binom{x+1}{0}\binom{y}{n}+\binom{x+1}{1}\binom{y}{n-1}+\cdots +\binom{x+1}{n}\binom{y}{0}. \qquad\qquad(\ast\ast)$$
We want to show this is equal to $\binom{x+y+1}{n}$.
The sum $(\ast\ast)$ can be written more compactly as
$$\sum_{k=0}^n \binom{x+1}{k}\binom{y}{n-k}.$$
Use the identity $(\ast)$. Then our sum is
$$\sum_{k=0}^n \left(\binom{x}{k}+\binom{x}{k-1}\right)\binom{y}{n-k}.$$ 
This is 
$$\sum_{k=0}^n \binom{x}{k}\binom{y}{n-k} +\sum_{k=0}^n \binom{x}{k-1}\binom{y}{n-k}.$$
The first sum is $\binom{x+y}{n}$ by the induction hypothesis. 
The second sum is equal to $\binom{x+y}{n-1}$. Again this is by the induction hypothesis. To see this, in the second sum let $j=k-1$. Then the second sum goes from $k=1$ (that is, $j=-1$, but there the binomial coefficient is $0$) to $k=n$, meaning that $j=n-1$. So the second sum can be written as $\sum_{j=0}^{n-1}\binom{x}{j}\binom{y}{n-1-j}$, and by the induction hypothesis this is $\binom{x+y}{n-1}$.  
We conclude that our sum $(\ast\ast)$ is equal to
$$\binom{x+y}{n}+\binom{x+y}{n-1}.$$
By $(\ast)$, this is 
$$\binom{x+y+1}{n},$$
and (finally) we are finished. 
Remark: The above is also a partial proof that combinatorial approaches are better. For sure they are a lot easier to type! A proof by calculation only tells us that a result is true. A combinatorial proof tells us why it is true. 
For the sake of humour, I complained excessively about the induction argument. It was in fact straightforward. It is natural to use the identity $(\ast)$. We can even think of $(\ast)$ as built into the definition of binomial coefficient, if we view binomial coefficients as being defined by Pascal's triangle.
A: By the binomial theorem, the RHS is the coefficient of $x^n$ in $(1+x)^{a+b}$. Likewise, the LHS is the sum over $k$ of the coefficient of $x^k$ in $(1+x)^{a}$ times the coefficient of $x^{n-k}$ in $(1+x)^{b}$. The polynomials $(1+x)^{a+b}$ and $(1+x)^{a}\times(1+x)^{b}$ coincide, hence the LHS equals the RHS.
