Euler, Erdős

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.