Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@anon, you should make that an answer. – Karolis Juodelė Mar 18 '13 at 8:00
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.