No time for a pithy preamble! This is the final post on this, and the proof is like a runaway train at this point, so we’re gonna need to focus if we wanna bring it in safely. (There’s a drinks trolley on board though, so you can still have a cuppa).
Switching the signs
We have this:
We want to make 1/(1+bx) look like 1/(1-bx) so we can get this as a series of terms. And the same for 1/(1+ax). Here’s ‘a’ and ‘b’ again:It’s not that tricky. All we need to do is make sure the minus signs are treated appropriately. Since the process is the same for both terms, I’ll show them side by side:
That’s the key to it, now we’re on easy street! But first, a wee bit about phi.
It’s the phi of the tiger, it’s the thrill of the phight…
Yeah, that was a dumb pun. Couldn’t help myself. Anyway. So I’ve been talking about this elusive phi, what the bloody hell is it? It first pops up in (written) history as far back as Euclid. He started with a basic definition: take a line split into two parts. If you set it up so that the ratio between the larger part and the smaller part, is the same as the ratio between the entire line and the larger part, then that ratio is phi.
Fair enough for a definition, you say, but where does that weird number with the square root of 5 occur? Well, let’s just say that line A is x. And line B is 1. So then Line C is x+1. So we’re saying that (x+1)/x, and x/1 are both phi. If x/1 is phi, then we just need to find x. It’s disarmingly simple:
- Obviously there’s two roots, depending on whether it’s plus or minus. The plus version is phi, or φ, which is 1.618…
- The reciprocal of φ (or 1/φ) is 0.618… which gets called Φ.
- Which is the same as φ-1.
- The minus version of φ, is -0.618… which is just -Φ.
- Which is the same as 1-φ!
- The reciprocal of that (1/-Φ) is (1/-φ).
- It’s confusing and incestuous as hell!
- On top of that, φ²=φ+1!
- More weird facts about phi here and here.
- I wanna avoid the mystical malarkey, but there’s about 2.5 million pages online about the phi / the Golden ratio if you’re interested. The proportion has been used in art and architecture and music, it’s found in nature, etc. Here’s a jumping off point from Wikipedia.
- If you only have 5 minutes to spare at a time, check out these three videos from Vi Hart (they are short and awesome. seriously).
We’ve already shown this:
So now, by replacing this ‘a’ with either value of phi, our generating function finally becomes:
Which looks like a bit of a mess. But remember that minus sign! Each term in the top parentheses has an equivalent term in the bottom parentheses! Like so:
That first term is simple. It’s just 1-1 = 0. Sorted! The next term:
That stuff in the red box? The coefficient of x to the nth power? That’s it! Sorted!! From the definition of generating functions way back in the first post:
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.
And remember, our equation has a 1/(root 5) outside the brackets, which means that each term is multiplied by it. So:
That’s it! That’s our closed-form solution for Fibonacci numbers! Choose a value n, and you will get the nth Fibonacci number! Guaranteed. (Unless you don’t use parentheses properly on your calculator). Tada!!
Oh yeah, almost forgot. Putting this as C++ code!
- Line 2: <cmath> includes defintions of pow (raising to a power), rounding, and square-root
- Line 3: <iomanip> includes definition of setprecision (for number of significant digits)
- Line 8: a new type, called ‘const’, combined with ‘double’, for declaring and defining phi. Const is a constant. So, rather than calculating phi every time on line 14, the compiler knows phi is a constant, calculates it once and stores it so that it can call the value directly without wasting time working it out each time!
- Line 10: cumulative-sum and newfib are both double as they will be getting their new values from line 14 which uses phi, which is a double. And also these numbers may become large, so.
- Lines 12-16 are the while-loop, all very logical.
- Line 13 uses ’round’, which rounds newfib up or down to the nearest integer. This is a ‘just-in-case’ safety measure. Depending on how big the numbers get, this may or may not be necessary. This is just to account for any potential floating-point errors.
- Line 14: sqrt is just square root. Simple. ‘pow(a,b)’ means raise a to the power of b.
- Note: instead of defining two different values for phi (1.618… and -0.618…), I just made the second term 1-phi, because 1-1.618…= -0.618…and it can call the same constant, which makes things tidier.
- Line 15: n+=3 is just the C++ shorthand way of saying n = n+3. I.e. ‘the thing to add to n, is 3’. For n = 0,1,2, fib(0,1,2) are 0, 1, 1. The first even Fibonacci number (2) is when n=3. So when n is multiples of 3, it’s even! We can calculate them directly and skip all the unnecessary numbers!
- Line 18: sets precision to 7 significant digits (or 6 decimal points when it gets big enough for an exponent).
And that’s it!