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

In my previous post, I explored the following cool formula for the nth term of the Fibonacci series. In this post, I’ll show why there are no square root fives after evaluation. 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*}

## How the square root fives cancel out.

One of the interesting things in this Fibonacci formula, is the $$\sqrt{5}$$’s that are all over the place, while the formula represents only integer values. Expanding the formula in binomial series shows us exactly why those terms all vanish. Consider the first few values of $$n$$ explicitly.
\label{eqn:fibonacci:160}
\begin{aligned}
F_1
&= \frac{ 1 + \sqrt{5} – \lr{ 1 – \sqrt{5} } }{ 2^1 \sqrt{5} } \\
&= \frac{ 2 \sqrt{5} }{ 2^1 \sqrt{5} } \\
&= 1,
\end{aligned}

\label{eqn:fibonacci:180}
\begin{aligned}
F_2
&= \frac{ 1 + 2 \sqrt{5} + 5 – \lr{ 1 – 2 \sqrt{5} + 5 } }{ 2^2 \sqrt{5} } \\
&= \frac{ 4 \sqrt{5} }{ 2^2 \sqrt{5} } \\
&= 1,
\end{aligned}

\label{eqn:fibonacci:200}
\begin{aligned}
F_3
&= \frac{ 1 + 3 \sqrt{5} + 3 (5) + \sqrt{5} 5 – \lr{ 1 – 3 \sqrt{5} + 3(5) – \sqrt{5} 5 } }{ 2^3 \sqrt{5} } \\
&= \frac{ 2 \lr{ 3 \sqrt{5} + \sqrt{5} 5 } }{ 2^3 \sqrt{5} } \\
&= \frac{ 3 + 5 }{ 2^2 } \\
&= 2.
\end{aligned}

In the general case, we have
\label{eqn:fibonacci:220}
\begin{aligned}
2^n \sqrt{5} F_n
&=
\sum_{k = 0}^n
\binom{n}{k}
{\sqrt{5}}^k

\sum_{k = 0}^n \binom{n}{k} (-\sqrt{5})^k \\
&=
2 \sum_{1 \le k \le n, \mbox{$k$ is odd}} \binom{n}{k} (\sqrt{5})^k \\
&=
2 \sqrt{5} \sum_{m = 0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{2 m + 1} 5^m,
\end{aligned}

so (for any $$n > 0$$),
\label{eqn:fibonacci:240}
F_n =
\inv{2^{n-1}} \sum_{m = 0}^{\lfloor (n-1)/2 \rfloor } \binom{n}{2 m + 1} 5^m.

Since only the odd powers of $$\sqrt{5}$$ in the binomial expansions survive, the root in the basement is obliterated every time, leaving only integers upstairs, and a power of two factor downstairs. It is still somewhat remarkable seeming that there is always a perfect cancellation of all the factors of two in the basement.