Take a recurrence relation, like the way the Fibonacci sequence is defined:

$a_n = a_{n-1} + a_{n-2}$, with $a_0 = 0$ and $a_1 = 1$.

I’m going to make up an infinite degree polynomial that looks like this:

$A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_k x^k + \dots$

… and figure out another way to write that polynomial.

If I multiply $A(x)$ by $x$, I get:

$xA(x) = a_0 x + a_1 x^2 + \dots + a_{k-1} x^{k} + \dots$

Same again:

$x^2A(x) = a_0 x^2 + a_1 x^3 + \dots + a_{k-2} x^{k} + \dots$.

Comparing coefficients, we can make most of the terms cancel out by combining these polynomials – the $x^k$ terms of $A(x) - xA(x) - x^2A(x)$ would all be zero (except near the very beginning) because of how the Fibonacci sequence is defined.

In fact, $(1 - x - x^2)A(x) = a_0 + (a_1 - a_0)x$ exactly, so $A(x) = \frac{a_0 + (a_1 - a_0)x}{1 - x - x^2}$. In our case, $a_0 = 0$ and $a_1 = 1$, so it’s $A(x) = \frac{x}{1-x-x^2}$

(This sort of trick can be done for any recurrence relation that relies on linear combinations of finitely many previous terms, and probably others as well.)

So what?

Now, the bottom of that definition doesn’t factorise.

Hold up, let’s be a bit more precise: it doesn’t factorise over the rationals. It factorises perfectly happily over the reals ((in general, the complex numbers might be needed)) as $(1 - \phi x)\br{1 + \frac{x}{\phi}}$.

Which means we can write it in partial fractions. It’s a bit ugly, but it works out fine enough: $\frac{x}{\br{1-\phi x}\br{1+\frac{x}{\phi}}} \equiv \frac{1}{\sqrt{5}}\br{\frac{1}{1+ \frac{x}{\phi}} - \frac{1}{1-\phi x}}$.

Still so what?

Hold on, I’m getting to it.

There’s a simple binomial expansion for $\frac{1}{1-kx}$ (it’s $1 + kx + k^2x^2 + \dots$). Here, we’ve got two of those, one with $k = -\frac{1}{\phi}$ and one with $k = \phi$.

So, the coefficient of $x^k$ in $A(x)$ is $\frac{1}{\sqrt{5}} \br{ \phi^k - \br{\frac{1}{\phi}}^k }$, which is Binet’s formula! (Remember, the coefficients by definition are the terms of the Fibonacci sequence.)

I suppose there’s a clincher here, too

But of course!

If you have any finite linear recurrence relation, you can come up with a generating function in a similar way: if you’ve got $P a_n + Q a_{n-1} + R a_{n-2} + \dots + Z a_{n-k}= 0$, then your generating function is $A(x) = \frac{a_0 + x a_1 + \dots x^{k-1} a_{k-1}}{P + Qx + \dots + Zx^{k}}$.

If you can find the zeros of the denominator – which you definitely can if $k \le 4$ – you can split it up into partial fractions (possibly requiring a little finesse with repeated roots) and come up with an explicit form for each of the terms – which are the elements of the sequence you defined recurrently!