This post provides a quick derivation of the fast Fibonacci doubling formulas, using the correspondence between Fibonacci numbers and the number of ways to climb $n$ steps taking 1 or 2 steps at a time.
The Fibonacci numbers are a sequence $\mathrm{Fib}(i)$ defined by $\mathrm{Fib}(1)=\mathrm{Fib}(2)=1$ and $\mathrm{Fib}(n+2)=\mathrm{Fib}(n+1)+\mathrm{Fib}(n)$.
The Fibonacci doubling formulas are:
$$\begin{eqnarray} \mathrm{Fib}(2n) &=& 2\mathrm{Fib}(n)\mathrm{Fib}(n+1) - \mathrm{Fib}(n)^2 \\ \mathrm{Fib}(2n+1) &=& \mathrm{Fib}(n+1)^2 + \mathrm{Fib}(n)^2 \end{eqnarray}$$
These formulas can be used to efficiently compute Fibonacci numbers (see the the end of the post for how). They are usually derived from a matrix power representation of Fibonacci numbers (or see one of my earlier posts for an alternative). This blog post gives a direct combinatorial derivation.
There’s a well-known algorithmic problem of counting the number of ways, $S(n)$, to climb $n$ steps, starting at the first step, ending exactly on the $n$th step, and taking 1 or 2 steps at a time. We see that $S(1)=S(2)=1$, and $S(n+2)=S(n+1)+S(n)$. Since this problem has the exact same recurrence relation as the Fibonacci numbers, $S(n) = \mathrm{Fib}(n)$.
We can count solutions to the steps problem in a different way, by dividing the problem in two (treating even and odd separately).
First the even case. Suppose we have $2n$ steps. The number of ways of taking these steps landing on the $n$th step is $S(n)S(n+1)$ (the number of ways of reaching step $n$, times the number ways of climbing $n+1$ steps). If a path doesn’t land on step $n$, then it must land on step $n-1$ and jump over step $n$ to land on step $n+1$. The number of such paths is $S(n-1)S(n)$. Thus $S(2n) = S(n)S(n+1) + S(n-1)S(n)$. Since $S(n-1)+S(n)=S(n+1)$, we have $S(2n) = S(n)S(n+1) + (S(n+1)-S(n))S(n) = 2S(n)S(n+1) - S(n)^2$.
The odd case is similar. Suppose we have $2n+1$ steps. By similar arguments to above, there are $S(n+1)S(n+1)$ paths that land on step $n+1$, and $S(n)S(n)$ paths that don’t. Thus $S(2n+1) = S(n+1)^2 + S(n)^2$.
Since $S = \mathrm{Fib}$, we’ve already derived the doubling formulas:
$$\begin{eqnarray} \mathrm{Fib}(2n) &=& 2\mathrm{Fib}(n)\mathrm{Fib}(n+1) - \mathrm{Fib}(n)^2 \\ \mathrm{Fib}(2n+1) &=& \mathrm{Fib}(n+1)^2 + \mathrm{Fib}(n)^2 \end{eqnarray}$$
For completeness, here’s how to use these formulae to quickly compute Fibonacci numbers with $O(\mathrm{log}_2(n))$ arithmetic operations.
def fib2(n):
"""fib2(n) returns fib(n), fib(n+1)"""
if n == 0:
return 0, 1
f0, f1 = fib2(n//2)
if n % 2 == 0:
# Even case.
return 2*f0*f1 - f0*f0, f0*f0 + f1*f1
else:
# Odd case.
# We need to return fib(2k+1), fib(2k+2)
# and we have f0=fib(k), f1=fib(k+1).
# The doubling formulas give:
# fib(2k) = 2*f0*f1 - f0*f0, fib(2k+1)=f0*f0 + f1*f1
# Then fib(2k+2) = fib(2k) + fib(2k+1) = 2*f0*f1 + f1*f1.
return f0*f0 + f1*f1, 2*f0*f1 + f1*f1
for i in range(20):
print(i, fib2(i)[0])
