Generating functions and binomial coefficients

Here I will show how to derive the binomial coefficients

\displaystyle \binom nk = \frac{n!}{k!(n-k)!}

using generating functions (using the approach from Wilf’s generatingfunctionology). For each nonnegative integer {n} and integer {k} with {0\leqslant k\leqslant n}, suppose {f(n,k)} is the number of {k}-element subsets of {\{1,2,\ldots, n\}}. Since each such subset of {\{1,2,\ldots, n\}} either contains {n} or does not, we have the recurrence

\displaystyle f(n,k) = f(n-1,k) + f(n-1,k-1)

for {n\geqslant 1}, with {f(n,0)=1} for {n\geqslant 0}. For each {n}, define the generating function

\displaystyle B_n(x) = \sum_{k=0}^n f(n,k)x^k.

Multiplying each side of the recurrence by {x^k} and summing over {k\geqslant 1} we get

\displaystyle \sum_{k=1}^n f(n,k)x^k = \sum_{k=1}^n f(n-1,k)x^k + \sum_{k=1}^n f(n-1, k-1)x^k,

and hence

\displaystyle B_n(x) - 1 = B_{n-1}(x) - 1 + xB_{n-1}(x),

so that

\displaystyle B_n(x) = (1+x)B_{n-1}(x)

for {n\geqslant 1}. Since {B_n(x)=f(0,0)=1}, it follows that

\displaystyle B_n(x) = (1+x)^n, \; n\geqslant0.

Since {B_n} is a polynomial, it is equal to its Taylor expansion:

\displaystyle B_n(x) = \sum_{k=0}^n \frac{B^{(k)}_n(0)}{k!}x^k.

It is clear that

\displaystyle B_n^{(k)}(x) = (n)_k (1+x)^{n-k},

where

\displaystyle (n)_k = \prod_{j=0}^{k-1}(n-j) = \frac{n!}{(n-k)!}.

Therefore {B_n^{(k)}(0)=(n)_k}, so that the coefficient of {x^k} in the Taylor expansion is

\displaystyle \frac{(n)_k}{k!} = \frac{n!}{k!(n-k)!}.

This is the familiar expression for {\binom nk}, and so

\displaystyle (1+x)^n = \sum_{k=0}^n \binom nk x^k,

the same result as that from the binomial theorem!

2 thoughts on “Generating functions and binomial coefficients

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s