## The Power of Generating Functions

In Pentagonal Number Theory, I touched on the topic of generating function but now I'll give examples of generating functions being used to find explicit solutions for recurrent relations. I think this was their primary purpose; Abraham de Moivre invented them when he tried to find the exact formula for the $$n^{th}$$ term of a sequence defined by a linear recurrence relation, like the Fibonacci Sequence.

Definition 1. The Fibonacci Sequence is $$1,1,2,3,5,8,13,\ldots$$ defined by the following recurrence: $F(0)=1; \quad F(1)=1; \quad F(n)=F(n-1)+F(n-2), ~ n\ge2$

Binet's Formula. $F(n) =\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$

Sidenote: It is named after Binet even though de Moivre discovered the formula a century before him.

Proof: We begin my defining the generating function for the sequence. $f(x) =1+x+2x^2+3x^3+5x^4+\cdots= \sum_{n=0}^\infty F(n)x^n$ To make use of the recurrence definition, we'll multiply $$f(x)$$ with $$x$$ and $$x^2$$. \begin{aligned} x f(x)=x+x^2+2x^3+3x^4+\cdots = \sum_{n=1}^\infty F(n-1)x^n \\ x^2f(x)=x^2+x^3+2x^4+3x^5+\cdots = \sum_{n=2}^\infty F(n-2)x^n \end{aligned} Looking at the summation form, we are tempted to set $$f(x)=xf(x)+x^2f(x)$$ but we have to adjust for the constant and $$x$$ terms since $$x^2f(x)$$ has neither of them.

$$xf(x)+x^2f(x)=x+\cdots$$ and $$f(x)=1+x+\cdots$$ thus, $$f(x)=1+xf(x)+x^2f(x)$$ or $f(x) = \frac{1}{1-x-x^2}$ $$1-x-x^2$$ can be factored into $$(1-\alpha x)(1-\beta x)$$ and $\alpha = \frac{1+\sqrt{5}}{2}, \qquad \beta = \frac{1-\sqrt{5}}{2}$ Now we split $$f(x)$$ using Partial Fractions $f(x)=\frac{1}{1-x-x^2} = \frac{A}{1-\alpha x} + \frac{B}{1 - \beta x}$ for some constants $$A, B$$. Comparing coefficients of the numerator and solving the equations gives, $A = \frac{\alpha}{\sqrt{5}}, \qquad B = -\frac{\beta}{\sqrt{5}}$ Going back to the generating function's partial fraction: \begin{aligned} f(x) &= \frac{1}{\sqrt{5}}\left(\frac{\alpha}{1 - \alpha x}\right) - \frac{1}{\sqrt{5}}\left( \frac{\beta}{1-\beta x} \right) \\ &= \frac{1}{\sqrt{5}}\left(\sum_{n=0}^\infty\alpha^{n+1}x^n\right) - \frac{1}{\sqrt{5}}\left(\sum_{n=0}^\infty\beta^{n+1}x^n\right) \\ &= \sum_{n=0}^\infty \frac{\alpha^{n+1}-\beta^{n+1}}{\sqrt{5}} x^n \\ &= \sum_{n=0}^\infty F(n)x^n, \qquad f(x) \text{ is the generating function.} \end{aligned} Finally, we have: $F(n) = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$

$$\Box$$

For integers $$a, b$$, any recurrence $$G(n)=aG(n-1)+bG(n-2)$$ has a closed form that can be found in a nearly identical proof. When $$b$$ is negative, then the generating function will not have a partial fraction decomposition without complex numbers. I'm guessing this shouldn't matter but I have not investigated it. You can try solving $$G(n)=G(n-1)-G(n-2)$$ and find out!

The following is a little more complicated generating function (known as exponential generating function) that will be used to solve the derangement problem. For example, $$n$$ traveling salesmen attend a conference and they leave their suitcases with the receptionist. At the end of the conference, the receptionist returns to each salesman a random suitcase. How many ways can the receptionist give each salesman the wrong suitcase? Such a case is called a derangement since nothing is in its right place. Another example, $$(3,1,2)$$ is a derangement of $$(1,2,3)$$ but $$(3,2,1)$$ is not.

Definition 3. A derangement is a permutation on a set $$S$$ with no fixed point. $$D(n)$$ denotes the number of derangements on a set with $$n$$ elements. Lastly, let $$D(0)=1$$.

Theorem 4. $D(n) = n!\sum_{i=0}^n \frac{(-1)^i}{i!}$

This theorem has an almost trivial proof using the Inclusion-Exclusion Principle that I may discuss in another post.

Proof: Before using a generating function, we must first find a recurrence relation on $$D(n+1)$$. Let us assume we are counting derangements on set $$S = {1, 2, 3, \ldots, n, n+1}$$. A derangement could sent $$1$$ to any of the other $$n$$ positions, let's say $$i$$. In this derangement, either $$1$$ and $$i$$ were swapped or not. If they were swapped, then we count the number of derangements on the remaining $$n-1$$ elements that have not been fixed yet, $$D(n-1)$$. If they were not swapped then only $$1$$ has been fixed and we count the derangments on $$n$$ elements, $$D(n)$$. Remember that there were $$n$$ positions for $$1$$, therefore: $D(n+1) = n(D(n)+D(n-1))$ Earlier methods will not work on this recurrence since it has a varying coefficient $$n$$. The exponential generating function is used instead: $\phi(x) = \sum_{n=0}^\infty \frac{D(n)}{n!} x^n$ This time we get to use differentiation as well as multiplying with $$x$$: \begin{aligned} \phi(x)&= \sum_{n=0}^\infty \frac{D(n)}{n!} x^n \qquad & \qquad \phi'(x)&= \sum_{n=0}^\infty \frac{D(n+1)}{n!} x^n \\ x\phi(x)&= \sum_{n=1}^\infty \frac{D(n-1)}{(n-1)!} x^n \qquad & \qquad x\phi'(x)&= \sum_{n=1}^\infty \frac{D(n)}{(n-1)!} x^n \end{aligned} Since $$\phi'(x)$$ has no constant terms, it follows from the recurrence that, $\phi'(x) = x\phi(x)+x\phi'(x)$ or $\frac{\phi'(x)}{\phi(x)} = \frac{x}{1-x} = -1 + \frac{1}{1-x}$ Integrating both side and using the fact $$\phi(0)=1$$: \begin{aligned} \ln(\phi(x))& = -x - \ln(1-x)\\ \phi(x) &= \frac{e^{-x}}{1-x} \\ &= \left(\sum_{n=0}^\infty x^n \right)\left(\sum_{n=0}^\infty \frac{(-x)^n}{n!}\right) \\ &= \sum_{n=0}^\infty \sum_{i=0}^n \frac{(-1)^i}{i!} x^n\\ &= \sum_{n=0}^\infty \frac{n!\sum_{i=0}^n \frac{(-1)^i}{i!}}{n!} x^n \\ &= \sum_{n=0}^\infty \frac{D(n)}{n!} x^n \end{aligned} As in the previous proof, compare coefficients of the two series to conclude. $$\Box$$

Particularly, this theorem implies $\lim_{n \rightarrow \infty} \frac{D(n)}{n!} = \frac{1}{e}$ So the chances that the receptionist will make a derangement while returning the suitcases are approximately $$37\%$$. Lastly, it also implies $D(n) = \frac{n!}{e} \text{ rounded to the nearest integer}$ PS: the value $$\frac{1}{e}$$ shows up in all sorts of places in probability and this could be an adventure for another post.