I love the smell of math proofs in the morning.

Obviously, each term of the Fibonacci sequence is built from the previous two terms. So this is a ‘recurrence/recursive relation’, in this case:

This means that finding fn involves finding all the numbers up to that point. What would be ideal is if we could have a closed-form solution. Basically an equation where we put in ‘n’ and get out the ‘nth’ value for that sequence. As it turns out, you can turn recurrence relations into closed-form solutions by using something called a ‘generating function’. In plain English:

A generating function is a series of terms, where the coefficients are the numbers of the sequence you’re looking at. For the Fibonacci sequence, it is:

F1, f2, f3, … , fn are the coefficients, which are just the Fibonacci numbers. What about the x terms? Those are just something called a formal power series. Series for obvious reasons. Power because each term is a higher power, x, x², x³ etc. Formal because the ‘x’s do not represent a particular value, and don’t actually need to. I’m still getting my head around the concept, but it’s a powerful trick, so I can roll with it.

Try to think of it like this: if they have specific values, then x is steve, x² is dave, x³ is bob. “Hey steve! ‘Sup, Dave? How’s it hangin’, Bob?” is informal. If these terms aren’t specific, you’d say “Good evening, gentlemen. Wouldst thou care for a dash of port?”, which is more formal. Or think of them as placeholders where it really doesn’t matter what, if any, meaningful value they have. Or failing that, go for the ‘appeal to authority’ argument: Taylor’s power series has been around since 1715, and Abraham de Moivre introduced generating functions back in 1730, so we’ve had almost 300 years to call them out on any bullshit and haven’t managed it yet. So, trust me, this works.

A generating function which uses a power series also just works really well because you can fiddle around with it and perform calculations on the entire series and essentially, simplify the expression until it’s something you can work with. Look what happens when you do something as simple as multiplying the entire generating function by x and x². Each power of x gets raised by either 1 or 2. If you realign the sequences by power, under the original sequence, you see something interesting:

What’s the big deal about this? Well, look at it term by term (column by column). f1x is, by definition, just:

F2 is just f1 or just 1. Since f0 is 0, then f2 = f1+f0. So far, so trivial. Now look at the third column:

f3x³, f2x³, f1x³. The top row is the sum of the lower two rows!

In general:

Check it!

Aha! But is this really that big a deal? All we did was express a series in terms of itself. How is that helpful?

Look at the leftmost column:

Ohhhhh! Starting to look a lot more useful now?

Fair enough. I’ll spell it out. Put all the f(x) terms on one side:

It’s going to click soon. Divide the right hand side by that longer expression, so that we once again have f(x) on the left-hand side. Since the whole point here is trying to work out a simple expression for f(x).

Bam. We just went from something that can have hundreds, thousands of terms, to a much much simpler, closed-form expression!

What’s next? Well, we’ll simplify that fraction even further and have a look at roots and factors, and that thing you always heard in math class called ‘completing the square’ but probably didn’t have explained well enough for you to know *why* the bloody hell it was called that. So the next time you hear characters on high school sitcoms soullessly repeating the mantra of “minus b, plus or minus the square root of: b squared minus four a c, all over two a”, it won’t sound like white noise.

Pingback: Episode VI: Return of the Dread Phi | hercles