1.5. Using Generating Functions to Prove Identities

A wide variety of combinatorial identities can be proven using generating functions. Without their help, we would typically rely on proof by induction and some messy Algebra.

This section is for illustrative purposes only. We won’t rely on it for our main applications, but it gives an impressive introduction to the power of the generating function side of the Taylor Series interpretation. As Yoda warned, if once you start down this path, forever will it dominate your proofs, seem amateur to you induction will. If you find yourself drawn to these methods, then a good reference to learn more is Herbert S. Wilf’s book generatingfunctionology.

The typical approach is to take a generating function whose coefficients are the combinatorial quantities of interest. Then use algebraic steps or other methods to rewrite the generating function so that the we can find its Taylor Series in a different way. Then by matching coefficients we arrive at a new identity.

1.5.1. Partial Fractions

Example 1.12

Consider the function

\[ f(x) = 0 + x + x^2 + 2 x^3 + 3 x^4 + 5x^5 + \cdots\]

for which \([x^n]f(x) = F_n\) is the \(n\)’th Fibonacci number. We saw in Example 1.4 that

\[f(x) = x/(1-x-x^2)\]

The quadratic formula shows us that the denominator factors as \(-(x+\phi)(x+\psi)\) where \(\phi = (1+\sqrt{5})/2\) and \(\psi= (1-\sqrt{5})/2\).

If we knew \(f(x)\) in a partial-fractions-like expansion \(c_1/(1-ax) + c_2/(1-bx)\), then we would be able to use the rule for a geometric series to write out the coefficients of \(f(x)\) explicitly. We will convert the factors in the denominator to resemble \(1-ax\). Since

\[\phi \psi = -1\]

the denoimator is

\[\begin{align*} -(x+\phi)(x+\psi) &= \phi\psi(x+\phi)(x+\psi)\\ &= (\psi x - 1)(\phi x -1)\\ &= (1-\psi x)(1-\phi x) \end{align*}\]

We now expand \(f(x)\) in partial fractions.

\[\begin{align*} \frac{x}{1-x-x^2} &= \frac{x}{(1 - \psi x )(1-\phi x)}\\ &= \frac{A}{1-\psi x} + \frac{B}{1-\phi x}\\ \Rightarrow x &= A(1-\phi x) + B(1-\psi x) \end{align*}\]

Setting \(x= 1/\phi\) gives

\[\begin{align*} 1/\phi &= 0A + B(1-\psi/\phi)\\ 1&=B(\phi-\psi)\\ \frac{1}{\phi-\psi}&=B\\ \frac{1}{\sqrt{5}} &=B \end{align*}\]

and using similar steps after setting \(x = 1/\psi \) gives

\[ A = -\frac{1}{\sqrt{5}} \]

So

\[\begin{align*} f(x) &= \frac{1}{\sqrt{5}} \left( \frac{1}{1-\phi x} - \frac{1}{1-\psi x}\right)\\ &= \frac{1}{\sqrt{5}} \left( (1 + \phi x + \phi^2x^2+\cdots) - (1 + \psi + \psi^2 x^2 + \cdots)\right)\\ &= \frac{1-1}{\sqrt{5}} + \frac{\phi-\psi}{\sqrt{5}}x^1 + \frac{\phi^2-\psi^2}{\sqrt{5}}x^2 + \cdots + \frac{\phi^n-\psi^n}{\sqrt{5}} x^n + \cdots \end{align*}\]

So \([x^n]f(x) = \frac{\phi^n - \psi^n}{\sqrt{5}}\), but it also equals \(F_n\). Hence we have proven

\[ F_n = \frac{\phi^n-\psi^n}{\sqrt{5}} \]

1.5.2. Binomial Expansions

Binomial coefficients often arise in combinatorial identities.

Example 1.13 (Vandermonde’s Identity)

Consider the identity

\[ (1+x)^{m+n}=(1+x)^m(1+x)^n \]

We expand both sides:

\[\begin{align*} \binom{m+n}{0} +& \binom{m+n}{1} x + \binom{m+n}{2}x^2 + \cdots + \binom{m+n}{m+n} x^{m+n}\\ =& \left( \binom{m}{0} + \binom{m}{1} x + \cdots + \binom{m}{m} x^m\right)\left( \binom{n}{0} + \binom{n}{1} x + \cdots + \binom{n}{n} x^n\right)\\ =& \binom{m}{0}\binom{n}{0}\\ & + \left(\binom{m}{1}\binom{n}{0} + \binom{m}{0}\binom{n}{1}\right)x \\ & + \left(\binom{m}{2}\binom{n}{0} + \binom{m}{1}\binom{n}{1} +\binom{m}{0}\binom{n}{2}\right)x^2 \\& + \cdots \\ =& \sum_{k=0}^\infty \sum_{r=0}^k \binom{m}{r}\binom{n}{k-r} x^k \end{align*}\]

if \(k>m+n\) then the right hand side turns out to be \(0\). For \(k \leq m+n\), we can match coefficients of \(x^k\) and conclude

\[ \binom{m+n}{k} = \sum_{r=0}^k \binom{m}{r} \binom{n}{k-r} \]

Remark 1.6 (The product \((1+x)^m(1+x)^n\))

To help illustrate the product \(\left( \binom{m}{0} + \binom{m}{1} x + \cdots + \binom{m}{m} x^m\right)\left( \binom{n}{0} + \binom{n}{1} x + \cdots + \binom{n}{n} x^n\right)\) we use a table:

		\(\color{blue}{\binom{m}{0}}\)	\(\color{blue}{\binom{m}{1}x}\)	\(\color{blue}{\binom{m}{2}x^2}\)	\(\color{blue}{\binom{m}{3}x^3}\)	\(\color{blue}{\binom{m}{4}x^4}\)	\(\color{blue}{\binom{m}{5}x^5}\)	\(\cdots\)
\(\color{blue}{\binom{n}{0}}\)		\(\binom{m}{0}\binom{n}{0}\)	\(\binom{m}{1}\binom{n}{0}x\)	\(\binom{m}{2}\binom{n}{0}x^2\)	\(\binom{m}{3}\binom{n}{0}x^3\)	\(\binom{m}{4}\binom{n}{0}x^4\)	\(\binom{m}{5}\binom{n}{0}x^5\)	\(\cdots\)
\(\color{blue}{\binom{n}{1}x}\)		\(\binom{m}{0}\binom{n}{1}x\)	\(\binom{m}{1}\binom{n}{1}x^2\)	\(\binom{m}{2}\binom{n}{1}x^3\)	\(\binom{m}{3}\binom{n}{1}x^4\)	\(\binom{m}{4}\binom{n}{1}x^5\)	\(\binom{m}{5}\binom{n}{1}x^6\)	\(\cdots\)
\(\color{blue}{\binom{n}{2}x^2}\)		\(\binom{m}{0}\binom{n}{2}x^2\)	\(\binom{m}{1}\binom{n}{2}x^3\)	\(\binom{m}{2}\binom{n}{2}x^4\)	\(\binom{m}{3}\binom{n}{2}x^5\)	\(\binom{m}{4}\binom{n}{2}x^6\)	\(\binom{m}{5}\binom{n}{2}x^7\)	\(\cdots\)
\(\color{blue}{\binom{n}{3}x^3}\)		\(\binom{m}{0}\binom{n}{3}x^3\)	\(\binom{m}{1}\binom{n}{3}x^4\)	\(\binom{m}{2}\binom{n}{3}x^5\)	\(\binom{m}{3}\binom{n}{3}x^6\)	\(\binom{m}{4}\binom{n}{3}x^7\)	\(\binom{m}{5}\binom{n}{3}x^8\)	\(\cdots\)
\(\color{blue}{\binom{n}{4}x^4}\)		\(\binom{m}{0}\binom{n}{4}x^4\)	\(\binom{m}{1}\binom{n}{4}x^5\)	\(\binom{m}{2}\binom{n}{4}x^6\)	\(\binom{m}{3}\binom{n}{4}x^7\)	\(\binom{m}{4}\binom{n}{4}x^8\)	\(\binom{m}{5}\binom{n}{4}x^9\)	\(\cdots\)

Each cell gives the product of the terms at the boundaries. Summing all of these together gives the product \((1=x)^m(1+x)^n\). The terms with the same power of \(x\) appear on diagonals.

1.5.3. Snake Oil

The following method is referred to as “snake oil” by Wilf due to switching of the order of summation. We first remind ourselves that \(\binom{N}{M} =0\) if \(M<0\) or \(M>N\) and \(\binom{0}{0}=1\).

Example 1.14 (Snake oil)

Consider the sum

\[ S_n=\sum_{k \geq 0} \binom{k}{n-k} \]

for \(n=0, 1, \ldots\).

We write

\[ g(x) = \sum_{n=0}^\infty S_n x^n \]

Then rearranging and switching the order of summations:

\[\begin{align*} g(x) &= \sum_{n=0}^\infty \sum_{k=0}^\infty \binom{k}{n-k} x^n\\ &= \sum_{k=0}^\infty \sum_{n=0}^\infty \binom{k}{n-k} x^n\\ &= \sum_{k=0}^\infty x^k\sum_{n=0}^\infty \binom{k}{n-k} x^{n-k}\\ &= \sum_{k=0}^\infty x^k\sum_{n=k}^\infty \binom{k}{n-k} x^{n-k}\\ &= \sum_{k=0}^\infty x^k\sum_{r=0}^\infty \binom{k}{r} x^{r}\\ &= \sum_{k=0}^\infty x^k(1+x)^k\\ &= \sum_{k=0}^\infty(x+x^2)^k\\ &= \frac{1}{1-x-x^2} \end{align*}\]

Here \(g(x)\) is \(1/x\) times the generating function of the Fibonacci sequence that we have seen in previous examples. Setting \(f(x)=x g(x)\), we have

\[ f(x) = F_0 + F_1 x + \cdots + F_n x_n + \cdots \]

and

\[ f(x) = 0 + S_0x + \cdots + S_{n-1} x^n +\cdots \]

So the \(n\)th Fibonacci number is given by

\[ F_n = S_{n-1}=\sum_{k \geq 0} \binom{k}{n-1-k} \]

(using the convention that \(F_0=0\) and \(F_1=1\))