## Guessing the nth Fibonacci number formula

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

My last two posts:

were both about a cool formula for the n-th term of the Fibonacci series.  Looks like I’m not done playing with this beastie.  A recap:

## Definition 1.1: Fibonacci series.

With $$F_0 = 0$$, and $$F_1 = 1$$, the nth term $$F_n$$ in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

## Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

## The guess.

We can rearrange the formula for the nth Fibonacci number as a difference equation
\label{eqn:fibonacci:260}
F_n – F_{n-1} = F_{n-2}.

This is a second order difference equation, so my naive expectation is that there are two particular solutions involved. We know the answer, so it’s not too hard to guess that the particular form of the solution has the following form
\label{eqn:fibonacci:280}
F_n = \alpha a^n + \beta b^n.

Given this guess, can we take some of the magic out of the formula, by just solving for $$\alpha, \beta, a, b$$? Let’s try that
\label{eqn:fibonacci:300}
F_0 = \alpha + \beta = 0,

\label{eqn:fibonacci:320}
\begin{aligned}
F_1 &= \alpha a + \beta b \\
&= \alpha \lr{ a – b } \\
&= 1,
\end{aligned}

and
\label{eqn:fibonacci:340}
\begin{aligned}
F_n
&= F_{n-1} + F_{n-2} \\
&=
\alpha \lr{ a^{n-1} + a^{n-2} }
-\alpha \lr{ b^{n-1} + b^{n-2} } \\
&=
\alpha a^{n-2} \lr{ 1 + a }
-\alpha b^{n-2} \lr{ 1 + b },
\end{aligned}

so
\label{eqn:fibonacci:360}
\begin{aligned}
a^2 &= a + 1 \\
b^2 &= b + 1.
\end{aligned}

If we complete the square we find
\label{eqn:fibonacci:380}
\lr{ a – \inv{2} }^2 = 1 + \inv{4} = \frac{5}{4},

or
\label{eqn:fibonacci:400}
a, b = \inv{2} \pm \frac{\sqrt{5}}{2}.

Out pop the golden ratio and it’s complement. Clearly we need to pick alternate roots for $$a$$ and $$b$$ or else we’d have zero for every value of $$n > 0$$. Suppose we pick the positive root for $$a$$, then to find the scaling constant $$\alpha$$, we just compute
\label{eqn:fibonacci:420}
\begin{aligned}
1
&=
\alpha \lr{ \frac{ 1 + \sqrt{5}}{2} – \frac{ 1 – \sqrt{5} }{2} } \\
&= \alpha \sqrt{5},
\end{aligned}

so our system \ref{eqn:fibonacci:280} has the solution:
\label{eqn:fibonacci:520}
\begin{aligned}
a &= \frac{1 + \sqrt{5}}{2} \\
b &= \frac{1 – \sqrt{5}}{2} \\
\alpha &= \inv{\sqrt{5}} \\
\beta &= -\inv{\sqrt{5}}.
\end{aligned}

We now see a path that will systematically lead us from the Fibonacci difference equation to the final result, and have only to fill in a few missing steps to understand how this could be discovered from scratch.

### Motivating the root-fives.

I showed this to Sofia, and she came up with a neat very direct way to motivate the $$\sqrt{5}$$. It follows naturally (again knowing the answer), by assuming the Fibonacci formula has the following form:
\label{eqn:fibonacci:440}
F_n = \inv{x} \lr{
\lr{ \frac{1 + x}{2}}^n

\lr{ \frac{1 – x}{2}}^n
}.

We have only to plug in $$n = 3$$ to find
\label{eqn:fibonacci:460}
\begin{aligned}
2 x
&= \inv{4} \lr{ 1 + 3 x + 3 x^2 + x^3 – \lr{ 1 – 3 x + 3 x^2 – x^3 } } \\
&= \inv{2} \lr{ 3 x + x^3 },
\end{aligned}

or
\label{eqn:fibonacci:480}
8 = 3 + x^2,

so
\label{eqn:fibonacci:500}
x = \pm \sqrt{5}.

Again the $$\sqrt{5}$$’s pop out naturally, taking away some of the mystery of the cool formula.

## The nth term of a Fibonacci series.

[If mathjax doesn’t display properly for you, click here for a PDF of this post.]

I’ve just started reading [1], but already got distracted from the plot by a fun math fact. Namely, a cute formula for the nth term of a Fibonacci series. Recall

## Definition 1.1: Fibonacci series.

With $$F_0 = 0$$, and $$F_1 = 1$$, the nth term $$F_n$$ in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

We can quickly find that the series has values $$0, 1, 1, 2, 3, 5, 8, 13, \cdots$$. What’s really cool, is that there’s a closed form expression for the nth term in the series that doesn’t require calculation of all the previous terms.

## Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

This is a rather miraculous and interesting looking equation. Other than the $$\sqrt{5}$$ scale factor, this is exactly the difference of the nth powers of the golden ratio $$\phi = (1+\sqrt{5})/2$$, and $$1 – \phi = (1-\sqrt{5})/2$$. That is:
\label{eqn:fibonacci:60}
F_n = \frac{\phi^n – (1 -\phi)^n}{\sqrt{5}}.

How on Earth would somebody figure this out? According to Tattersal [2], this relationship was discovered by Kepler.

Understanding this from the ground up looks like it’s a pretty deep rabbit hole to dive into. Let’s save that game for another day, but try the more pedestrian task of proving that this formula works.

### Start proof:

\label{eqn:fibonacci:80}
\begin{aligned}
\sqrt{5} F_n
&=
\sqrt{5} \lr{ F_{n-2} + F_{n-1} } \\
&=
\phi^{n-2} – \lr{ 1 – \phi}^{n-2}
+ \phi^{n-1} – \lr{ 1 – \phi}^{n-1} \\
&=
\phi^{n-2} \lr{ 1 + \phi }
-\lr{1 – \phi}^{n-2} \lr{ 1 + 1 – \phi } \\
&=
\phi^{n-2}
\frac{ 3 + \sqrt{5} }{2}
-\lr{1 – \phi}^{n-2}
\frac{ 3 – \sqrt{5} }{2}.
\end{aligned}

However,
\label{eqn:fibonacci:100}
\begin{aligned}
\phi^2
&= \lr{ \frac{ 1 + \sqrt{5} }{2} }^2 \\
&= \frac{ 1 + 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 + \sqrt{5} }{2},
\end{aligned}

and
\label{eqn:fibonacci:120}
\begin{aligned}
(1-\phi)^2
&= \lr{ \frac{ 1 – \sqrt{5} }{2} }^2 \\
&= \frac{ 1 – 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 – \sqrt{5} }{2},
\end{aligned}

so
\label{eqn:fibonacci:140}
\sqrt{5} F_n = \phi^n – (1-\phi)^n.

# References

[1] Steven Strogatz and Don Joffray. The calculus of friendship: What a teacher and a student learned about life while corresponding about math. Princeton University Press, 2009.

[2] James J Tattersall. Elementary number theory in nine chapters. Cambridge University Press, 2005.