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
        # 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])
Paul Hankin Written by:

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.

comments powered by Disqus