Season 9 Episode 12

In this episode, Ola from the OxWoCS student society tells us about Fibonacci numbers, and we investigate some algorithms to assess their computational complexity!

Watch on YouTube

Further Reading

Code

If you want a copy of Ola’s code, you can download that here; oomc_fib.txt (note that this has been downloaded as a text file; change the file extension to ipynb to change it back to a Python notebook).

You probably shouldn't run code that you've downloaded off the internet though; who knows what that will do to your computer? Here's how you can run it on someone else's computer (Google's!). If you have a Google account, then you can run the Python notebook online with Google Colab; head to that page, select upload and choose this file (with ipynb as the file extension), then open it in Google Colab. Click the little play buttons down the left-hand side to run each block of code. Some of them are very slow, as we discussed!

Better algorithms

If you know Haskell, you might enjoy this list of Haskell implementations of the Fibonacci sequence.

If you don’t know Haskell... I think you’re in the majority! Haskell is a programming language that can handle infinite lists, among other mathematical conveniences. At Oxford, we teach it to first-year Computer Science students. You can get a sense of what it’s like from this (charmingly named) guide; Learn You a Haskell for Great Good!. (note that the guide doesn't have any exercises; you're encouraged to play along and make up your own exercises as you go).

Computational Complexity

While we were talking about the potential runtime of different algorithms in the episode, we used some language from complexity theory. I hope that expressions like "linear time" to mean "time proportional to the size of the input" made sense. Wikipedia has a big list of the time complexity of various algorithms.

I'd also like to link you to resources about computational complexity theory. I'm going to throw you a curveball by linking to a Philosophy textbook; the Stanford Encyclopedia of Philosophy has an extraordinarily detailed (and free and online!) article about this topic.

Solving Recursion Relations

If a sequence \(x_n\) obeys some relationship like \(x_n= a \times x_{n-1} + b \times x_{n-2}\), where \(a\) and \(b\) are constants, and if we’re given values for \(x_0\) and \(x_1\), then it would be nice if we could find a formula for \(x_n\) in terms of \(n\), so that we could avoid calculating with the recursion relation.

The solutions to equations like this take the form \(x_n = A \lambda^n+B \mu^n\) where \(A\) and \(B\) are constants, and where \(\lambda\) and \(\mu\) are the roots of the quadratic \(x^2=ax+b\), provided that quadratic has distinct roots. You might like to check that if \(x_n\) has that form for each value of \(n\), then the sequence satisfies the recursion relation. You’ll need to use the facts that \(\lambda^2=a\lambda+b\) and \(\mu^2=a\mu +b\) to simplify things along the way.

This result is not at all obvious, and it’s the sort of thing that I’d love to prove with matrices (the values \(\lambda\) and \(\mu\) are eigenvalues of the constant matrix transformation that takes the vector \(\binom{x_{n-1}}{x_{n-2}}\) to the vector \(\binom{x_n}{x_{n-1}}\), but I don’t think everyone’s ready for matrices yet.

Binet Formula

For Fibonacci numbers, the characteristic equation is \(x^2=x+1\) and the roots are \(\frac{1}{2}\left(1\pm\sqrt{5}\right)\). The positive root is the golden ratio \(\phi\), and (by the magic of the golden ratio, you could say), the other root is \(-1/\phi\).

We work out the values of \(A\) and \(B\) by thinking about what happens for \(n=0\) and \(n=1\). This gives the frankly surprising formula $$F_n=\frac{1}{\sqrt{5}}\left(\phi^n+\left(-\frac{1}{\phi}\right)^n\right)$$

This is called Binet’s formula.

The Art of Problem Solving website has an article that derives this formula while deftly avoiding the general theory of recurrence relations that I’ve hinted at above. Because it’s Art of Problem Solving, there’s also a longer proof with calculus!

More Fibonacci Numbers

This seems like a good moment to mention that the Fibonacci numbers were known to Indian mathematicians hundreds of years before Fibonacci was born, partly because of a particular counting problem concerning long and short syllables.

See (for example) Wikipedia for a description of the problem, and see if you can work out for yourself why the solution is this familiar sequence.

Binary Tree

We saw a tree structure near the end of the episode, where (to start off, at least!) each node has two “children” (nodes underneath). That’s a semi-famous structure called a binary tree. If you grow it upwards instead of downwards (i.e. if you invert the binary tree), then it even looks a bit like a tree.

I’d like to show you my favourite binary tree, one that includes some geometry too. It’s called the Pythagoras Tree and it’s a fractal.

Semi-recently, someone’s managed to calculate the area of the Pythagoras tree; see this webpage for the details of their calculation, which did involve a computer.

Coding Challenges

For more computational challenges, Ola recommends Advent of Code, a series of coding challenges published each December, with rapidly increasing difficulty.

I always like to recommend Project Euler for problems where you need to think first and write some code second.

More golden ratio facts on OOMC

We looked at pentagonal geometry once; Pentagon Geometry | OOMC S5 ep3.

And we looked at lots more golden ratio things once, including phi-nary, which is a bit like binary but with the golden ratio instead of 2. See the YouTube video here; Solid Gold | OOMC S8 ep 3 | YouTube. It’s the only time we’ve had a copyright strike for OOMC!