# Generating functions - combinatorics

Use generating functions to prove that for $n \geq 0$, $$\sum^n _{k=0}\binom{x}{k}\binom{y}{n-k} =\binom{x+y}{n}$$

Any help would be appreciated since I don't get anything of these.....

• @anon, you should make that an answer. – Karolis Juodelė Mar 18 '13 at 8:00

The idea behind using generating functions to prove combinatorial identities is to make both sides the coefficients of some (formal) power series or polynomial, then simplify/manipulate both sides until it is an obvious identity of functions. When it comes to binomial coefficients, the key type of polynomial to keep in mind is that which appears in the binomial theorem. Here, when you multiply both sides by $t^n=t^{n−k}t^k$ and sum over $n$, what does it look like? Namely, this:
$$\sum_{n\ge0}\sum_{k=0}^n{x\choose k}{y\choose n-k}t^kt^{n-k}=\sum_{n\ge0}{x+y\choose n}t^n$$
You should recognize the latter as $(1+t)^{x+y}$ (a dehomogenized version of $(u+v)^m$ as seen in the binomial theorem), and the first looks like its summands are products of those of $(1+t)^x$ and the other $(1+t)^y$; verify that indeed the left side is $(1+t)^x(1+t)^y$, by observing that as $n$, $k$ and $n-k$ range in the summation, the two powers of $t$ range over every possible pair (although the binomial coefficients will be zero when $n>x,y$), so it can be rewritten as
$$\sum_{a\ge0}\sum_{b\ge0}{x\choose a}t^a{y\choose b}t^b.$$