Show $\sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k} = \binom{x+y}{n}$.

Question

For $n\ge 0$, show $\sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k} = \binom{x+y}{n}$.

Over a well ordered set of non-negative integers, induction can be used.

Base case: $n=0$
$\binom{x}{0} \binom{y}{0} = 1.\frac{(y)!}{(y)! \,\,(0)!}=1$.

Taking the rhs, get : $\binom{x+y}{0} = 1$.

Induction hypothesis: it is true for natural number $n$.

So, $\sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k} = \binom{x+y}{n}$

Inductive step: need show for next natural $n+1$

$\sum_{k=0}^{n+1} \binom{x}{k} \binom{y}{n-k+1} = \binom{x+y}{n+1}$

This should lead to :

$\binom{x+y}{n} + \binom{x}{n+1}\binom{y}{0}= \binom{x+y}{n+1}$

get on lhs:

$\binom{x+y}{n} + 1.\binom{x}{n+1}$

$\implies \frac{(x+y)!}{n!(x+y-n)!} + \frac{x!}{(n+1)!(x-n-1)!}$

Please help to proceed further, or suggest alternative approach.

Answer 1

$$S=\sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k}$$ $$S=\sum_{k=0}^{n}[t^k]~ (1+t)^x~ [t^{n-k}]~ (1+t)^y$$ $$S=[t^n] (1+t)^{x+y}={x+y \choose n}.$$ Here $[t^j]f(t)$ means co-efficient of $t^j$ in $f(t).$

Answer 2

There are much better proof strategies in my opinion, but here's an inductive proof of the Vandermonde convolution identity.