Hey! Welcome back to (hopefully) the last post in this 3(ish) part series.

Proof of formulae

Recurrence relations method

Here’s an explanation behind the recurrence relations method.

The idea is that we make a guess in terms of what the recurrence relation closed form should look like (spoiler, we think it’ll be an exponential function). Based on this, we try to find the underlying polynomial and solve for the roots of this.

As you can see in the post, we figured out the roots that solve the relation would be $r_1 = \phi$ and $r_2 = 1 - \phi$.

Then based on the initial values, you can figure out the constants at the front.

Generating functions method

In Calculus 2, you might have encountered power series. They’re a little like Taylor series, except instead of having the constant for each term be $\frac{f^{(n)}(a)}{n!}$ (the $n$th derivative at $a$, over $n$ factorial), you can let it be any sequence. So they’ll be in the form of:

$$\sum^{\infty}_{i=0} a_n x^n$$

If we let $a_n = \text{Fib}_n$, then we get “the Fibonacci generating function” $F(x)$. To find the closed form follow these steps:

  • Manipulate the formula to get $F(x) = \frac{1}{1-x-x^2}$
  • Use partial fraction decomposition to get it into two terms.
  • Since they’re both in the form of $\frac{a}{1 -r}$, use the geometric series formula to get an expansion for them.
  • By equating the new formula with the original formula for $F(x)$, you can notice that $a_n = $ (something).
  • That’s the closed form!

Full proof here.

Matrix diagonalization method

Consider the vector \(\begin{pmatrix} \text{Fib}_{n+1} \\ \text{Fib}_{n}\end{pmatrix}\).

You get the following construction (using the definition of Fibonacci numbers):

$$\begin{bmatrix}\text{Fib}_{n+1} \\ \text{Fib}_{n} \\\end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0\\ \end{bmatrix}\begin{bmatrix} \text{Fib}_{n} \\ \text{Fib}_{n-1}\end{bmatrix}$$

as seen from the last blog post.

As seen in the last post, the formula can now be adjusted to look like this:

$$\begin{bmatrix}f_{n+1} \\ f_{n} \\\end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0\\ \end{bmatrix}^n\begin{bmatrix} 1 \\ 0\end{bmatrix}$$

Notice that the inner matrix (let’s call it $A$), can be diagonalized. Meaning, there exists an invertible matrix $P$, and a diagonal matrix $D$ such that $A = PDP^{-1}$.

Why is this important? Well, by induction, we can prove that $A^n = PD^nP^{-1}$. Since diagonal matrices are easy to matrix multiply (you just exponentiate each term as it is diagonal), this is really easy to compute.

Finally, just matrix multiply the three terms ($PD^nP^{-1}$), and you get the exact same closed form formula!

Here’s a walkthrough for it.

Aside

Some of you (if you go through the process) notice that the quadratic ($1 - x - x^2$) found in the first method, is the reciprocal of the rational function found in the second method!

Also, it’s the characteristic polynomial of the matrix $A$, found in the last method!

This comes up as this is the function with roots $\phi$ and $-\frac{1}{\phi} = 1 - \phi$.

Conclusion

The Fibonacci series of blog posts is over! While I’d love to keep talking about the Fibonacci numbers, there are so many other things to talk about! Hope anyone who has been following this series, takes a look at the other posts I will publish!