Deriving the Fibonacci doubling formulas combinatorially

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])

Programming since 1981, professionally since 2000. I’ve a PhD in programming language semantics but these days I prefer programming in Go, C, and Python. I’ve worked mostly on games and large-scale server software.