# 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

-
The thing is symmetrical, why not go from $(x,y)$ to $(x+1,y)$, also $(x,y+1)$? The proofs will be essentially identical. For going to $(x+1,y)$, I would use the easily verified binomial coefficient identity $\binom{x+1}{k}=\binom{x}{k}+ \binom{x}{k-1}$. I assume you are perfectly aware that the identity you are trying to prove has a very quick combinatorial proof. – André Nicolas Jan 31 '12 at 6:01
Thanks for your answer. Well, I tried the other way around but I found easier to get the first step of the induction using P(b,a) instead. Does the proof you have in mind involves induction?... because as you stated, I know there is a proof by using the fact that $q_{0}+q_{1}+...+q_{n}$ when $q_{k}$ is the hypergeometric formula, which I think it's the combinatorial proof you're referring to. – Robert Smith Jan 31 '12 at 6:07
We have a group of $a$ men and $b$ women. Want to choose a team of $n$ people. Obviously there are $\binom{a+b}{n}$ ways to do this. Count another way. Could have $0$ men $n$ women, or $1$ man $n-1$ women, and so on. By the way, the convention is that $\binom{x}{y}=0$ if $x<y$, else the formula does not make sense if for example $a=10$, $b=10$, and $n=13$. The proof I was thinking of going from $(x,y)$ to $(x+1,y)$ is induction, since that is what you asked for. But the above combinatorial proof is vastly more pleasant! – André Nicolas Jan 31 '12 at 6:12
Yeah, that problem leads to the hypergeometric distribution (en.wikipedia.org/wiki/Hypergeometric_distribution). – Robert Smith Jan 31 '12 at 6:17
You need not worry about that at this moment, since it should be clear that the sum on the left counts the same thing as the expression on the right, so the two are equal. – André Nicolas Jan 31 '12 at 6:25

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.

-
Quel courage... :-) – Did Jan 31 '12 at 7:15
Wow, it seems the change of variable (from a,b to x+1, b) helps a lot. Thank you very much :-) – Robert Smith Jan 31 '12 at 7:23
+1 for the corollary! – Myself Jan 31 '12 at 11:05

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.

-
I agree with @André in comments that induction is not needed here. – Did Jan 31 '12 at 6:25
Didier, thanks a lot. As I said, I already proved this one by other means but this problem asks explicitly for induction (at least, Feller asks for it). – Robert Smith Jan 31 '12 at 6:28
Then the two first sentences of André's first comment indicate a much simpler induction scheme and how to prove it. – Did Jan 31 '12 at 6:36
As he didn't answer my question, I didn't know whether he was referring to using induction. I will look into that, then. Thanks! – Robert Smith Jan 31 '12 at 6:41
Yeah, do that, good idea... – Did Jan 31 '12 at 6:57