# 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

## 1 Answer

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.$$

The logical validity in going from an unknown identity we wish to prove towards an obvious identity of functions or polynomials or power series is that we want our manipulations and transformations we applied to be reversible so that the unknown identity also logically follows from the obvious one we achieved from it.

• I must say that this is an excellent explanation. I would have just written down a couple of formulas but this answer provides a path to think about things. For instance, one could think about the formula using (1+x)^(-a) and get an identity for (y choose b) above. – rrogers May 20 '17 at 19:58