This is a part 2 of a 3 part series on the Fibonaccci numbers. This section contains more math, but personally it’s more computer science because it deals with the problem presented in the last post (solving for the $n$th Fibonacci number).

Recurrence relations

We’re now into my first year, winter semester of university. I feel weathered from the first semester, but eager to get into some actual material. This content is directly ripped from CSC240H1 (Enriched Introduction to the Theory of Computation), taught by James Cook. At last, I encounter the Fibonacci numbers, but in a completely new light!

So it turns out with the definition we presented in the last post, the Fibonacci numbers follow what is called a recurrence relation. A recurrence relation is exactly what is outlined in the last post. Anything where you can define the initial terms (in our case, the first two Fibonacci numbers), and you can build the rest of it using knowledge of the preceding values (in our case, building a new Fibonacci number using the last two).

Hearing all these new words was definitely really intimidating for me (especially the words that are about to come), but it was really exciting to hear this from a more theoretical point of view.

The cool thing about our problem relating to a larger class of problems is that there’s probably some math dude who’s solved it. In our case, that’s totally right. I’m going to save a long explanation here, but the formula we have for the Fibonacci numbers is what is called a linear homogeneous recurrence relation of order 2 with constant coefficients.

Let us break down the individual terms.

We already know what a recurrence relation is.

linear means that each new term is dependent on the last term directly. No exponents, and no dangling terms off of the side.

homogeneous means that isn’t an additional dangling term (like $n^2$), at the end.

of order 2 means that we only look at two terms back. With the method we’re using (not shown in this post), we can only use this if our order does not depend on $n$.

constant coefficients means that the coefficients (the numbers that each term is being multiplied by), doesn’t depend on $n$. In our case, our coefficients are both 1.

With this specific type of relation, you can do some math (which is outside of the scope of this blog post) and get the closed form! (If we let the sequence start at 0, we get this:)

$$\text{Fib}_n = \frac{1}{\sqrt 5} \left(\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 - \sqrt 5}{2}\right)^n\right)$$

Sweet, huh? Looks like we’re done here. We got a Fibonacci closed form, we’re all good.

Note: The golden ratio is in this formula! It’s no surprise, and I’ll explain later why this appears. Note that the other number $\frac{1 - \sqrt 5}{2} = 1 - \phi = -\frac{1}{\phi}$. It’s quite bizarre, but does come up when we analyze about the golden ratio itself.

Induction

Not so fast. How do we know that formula works? To prove that, we’re going to what is called a proof by induction.

Induction is a process where we prove that the formula works for a base case, and then we prove it works for a general case (often called the induction step).

There’s a very nice ladder analogy. If you can climb onto the first rung of a ladder, and if you are on a rung of the ladder, you can climb to the next rung, is that enough to show that you can climb any ladder? Well, mathematically, yes. Mostly because we don’t have things like external events (like being struck by lightning, or a crippling fear of heights) in math.

Induction follows similar. If we have some property $P$, that we want to prove for all counting numbers ($1, 2, 3, 4, 5, \dots$), we can prove it inductively as follows:

  • Prove the property for the $1$ case, also known as $P(1)$. (This is called the base case)

  • Prove that if the property is true for the $n$ case (for any counting number $n$), then the property also holds in the $n+1$ case.

And that’s all induction is! Not thoroughly convinced? Just think of it this way. If you want to check if the property is true for any counting number (say 1000, or even 1 000 007), we know that:

  • $P(1)$ is true (first step)
  • if $P(1)$ then $P(2)$ (second step, since $1$ is a counting number)
  • if $P(2)$ then $P(3)$ (second step, since $2$ is a counting number)
  • if $P(3)$ then $P(4)$ (second step, since $3$ is a counting number)
  • …
  • if $P(99)$ then $P(100)$ (second step, since $99$ is a counting number)
  • …
  • if $P(1 000 006)$ then $P(1 000 007)$ (second step, since $1 000 006$ is a counting number)

So we should be able to conclude that whatever your number is, the property must hold for it too (so long as it is a counting number).

If this looks like domino logic, that’s because the idea is very similar.

I’m going to now prove that the formula is true (for the Fibonacci numbers) for all counting numbers $n$. This might be a little confusing, so you’re totally free to jump to the next step.

Proof

For any counting number $n$, let $P(n) = $ “the $n$th Fibonacci number, is equal to that formula (written above).”

  • Base Case: If $n = 1$, we can verify that is true, as we know the first Fibonacci number to be 1.
$$\frac{1}{\sqrt 5} \left(\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 - \sqrt 5}{2}\right)^n\right) = \frac{1}{\sqrt 5} \left(\left(\frac{1 + \sqrt 5}{2}\right) - \left(\frac{1 - \sqrt 5}{2}\right)\right) = \frac{1}{\sqrt 5} \left(\frac{2\sqrt 5}{2}\right) = 1$$

So we can conclude that $P(1)$! This formula indeed holds for the first Fibonacci number.

We can also do this if $n = 2$.

$$\begin{aligned} \frac{1}{\sqrt 5} \left(\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 - \sqrt 5}{2}\right)^n\right) &= \frac{1}{\sqrt 5} \left(\left(\frac{1 + \sqrt 5}{2}\right)^2 - \left(\frac{1 - \sqrt 5}{2}\right)^2\right)\\ &= \frac{1}{\sqrt 5} \left(\left( \frac{1 + 2\sqrt{5} + 5}{4}\right) - \left(\frac{1 - 2\sqrt{5} + 5}{4}\right)\right)\\ &= \frac{1}{\sqrt 5}\left(\frac{4\sqrt{5}}{4}\right)\\ &= 1\end{aligned}$$

Once again, we get the result we want. So we can conclude $P(2)$!

  • Induction Step: Now, for any counting number such that $n > 2$, we will assume that $P(n - 1)$ and $P(n-2)$ are true. We want to prove that $P(n)$ is true. I’ll leave this as an exercise to those who are reading, it’s pretty fun!

If you successfully proved the induction step, then we’ve shown that the formula is true!

Conditioning

However, there are some caveats to the above formula. In the summer of my first year, I took a course called CSC336H1 (Numerical Methods), which concerns itself with numerical calculations in computers and how to deal with approximations. This helped me give some insight as to why we’re not at the best solution yet.

A keen reader might point out that the formula uses $\sqrt 5$, which is an irrational number. That means, it’s not describable as a ratio between two counting numbers (we include $0$ and negative counting numbers as well). Why is this bad?

Well, that means that no matter how we try to work with the number, we will only ever have an approximation of $\sqrt 5$.

This… is admittedly kind of yucky. If the approximation of the square root has an error of $\epsilon$, this will propagate throughout our answer (plug in $\sqrt 5 + \epsilon$ everywhere you see $\sqrt 5$, and you’ll see that your answer is muddied.) This gets really bad when you have bigger and bigger Fibonacci numbers that you want to compute.

In addition, computers can’t store incredibly precise numbers as well! This makes our above solution (while really nice), also possibly subject to error propagation for large enough inputs.

In the next post, I’ll be explaining about some more ways to solve Fibonacci, and also how to measure how efficient we are.

(Author’s note: I’m splitting up this blog post since it’s quite long-winded anyways.)

Footnote: Sequences and sums

Side fact I found! In Calculus 2, we talk about sequences and series (infinite summations of the sequences), and the Fibonacci numbers certainly form a sequence. So while playing around with the definition of Fibonacci numbers, you can see that, using partial sums:

\[\text{Fib}_{n+2} - 1 = \sum_{i = 0}^{n} \text{Fib}_i\]

This basically says that the first $n$ Fibonacci numbers are equal to the $n+2$th Fibonacci number minus 1. I won’t prove this, but you can try to check it out on your own to see why it’s true. It’s a fun induction exercise!