# 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”

1. Cool way to look at it!

Like