The Fibonacci Sequence

F(n)={0,n=01,n=1F(n−1)+F(n−2),n>1F(n)=\begin{cases} 0, &n=0 \\ 1,&n=1 \\ F(n-1)+F(n-2),&n>1 \end{cases}

This is the Fibonacci sequence, something we have all seen from elementary school onward. I ran into it again while reviewing data structures recently, and it still feels surprisingly interesting.

Let us look at the complexity of computing it with plain recursion:

1
2
3
4
5
int f(n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return f(n - 1) + f(n - 2);
}

The recurrence relation is immediate:

F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2)

One intuitive way to think about it is to decompose each result into combinations of 1 and 2. Every new way of combining them creates another branch in the recursion tree, and every branching point corresponds to another operation.

If we split n into two parts, t and n-t, we get:

Sn=∑t=0n(n+t2)!t!(n−t)!=∑k=0n/2(n−kk)S_{n=}\sum^n_{t=0} \frac{\left( \frac{n+t}{2} \right)!}{t!(n-t)!}=\sum^{n/2}_{k=0}\dbinom{n-k}{k}

And since

(n−kk)=(n−k−1k)+(n−k−1k−1)\dbinom{n-k}{k}=\dbinom{n-k-1}{k}+\dbinom{n-k-1}{k-1}

we obtain

Sn=Sn−1+Sn−2,S0=1,S1=1S_{n}=S_{n-1}+S_{n-2}, \quad S_{0} = 1, \quad S_{1}=1

So S_n is also a Fibonacci sequence, and in fact:

Sn=F(n+1)S_{n}=F(n+1)

That is the fun part: the operation count is essentially the next Fibonacci number.

If you draw the recursion tree for F(n), the number of branching nodes is close to the number of leaf nodes by the usual properties of binary trees. The leaves are only F(0) and F(1). The value F(n) itself counts all the F(1) leaves, and the number of F(0) leaves is:

F(n+1)−F(n)=F(n−1)F(n+1)-F(n)=F(n-1)

Push that process forward by one more step and the picture becomes even clearer: every original F(0) becomes an F(1), and every original F(1) produces a new F(1) and a new F(0).

That is exactly the same logic behind the classical rabbit-breeding interpretation of the Fibonacci sequence. F(0) behaves like a young rabbit, which becomes an adult one step later, namely F(1). Each adult rabbit then produces a new young rabbit, so after one time step you have the original F(1) plus a newly created F(0). That is the reproduction model in a very direct form.

So the Fibonacci sequence is really the accumulated result of repeated underlying reproduction. Once you think in that way, a useful mapping appears:

(F0,F1)↦(F1,F0+F1)(F_{0}, F_{1}) \mapsto (F_{1},F_{0}+F_{1})

In vector form:

vn=(anbn)an=F0,bn=Fnv_{n}=\begin{pmatrix} a_{n} \\ b_{n} \end{pmatrix} \quad a_{n}=F_{0}, \quad b_{n}=F_{n}

vn+1=(0111)vnv_{n+1}=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}v_{n}

If you have studied linear algebra, you already know what that matrix means:

F0=an+1=Fn,Fn+1=bn+1=F0+FnF_{0}=a_{n+1}=F_{n}, \qquad F_{n+1}=b_{n+1}=F_{0}+F_{n}

So the entire iteration is encoded by the matrix

M=(0111)M=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

which is the Fibonacci Q-matrix. Its eigenvalues are

φ=1±52\varphi = \frac{1\pm\sqrt{ 5 }}{2}

and after the usual diagonalization steps we get

Q=S(φ100φ2)S−1,Qn−1=S(φ1n−100φ2n−1)S−1Q=S \begin{pmatrix} \varphi_{1} & 0 \\ 0 & \varphi_{2} \end{pmatrix} S^{-1},\quad Q^{n-1}=S \begin{pmatrix} \varphi_{1}^{n-1} & 0 \\ 0 & \varphi_{2}^{n-1} \end{pmatrix} S^{-1}

Apply that to v_1 and you recover the closed form:

Fn=φ1n−φ2n5F_{n}=\frac{\varphi_{1}^n-\varphi_{2}^n}{\sqrt{ 5 }}

So in terms of complexity, we only care about the dominant term, which means

Fn∼φ1nF_{n}\sim \varphi_{1}^n

That is,

Fn∼1.618nF_{n}\sim 1.618^n

which is the golden ratio. Nice.

Afterword

Of course there are much faster algorithms for computing Fibonacci numbers. But this way of thinking is fun, and it connects nicely back to sequence limits too.

That is exactly why this kind of question is interesting:

an=pan−1+qan−2, a1>0, a2>0, p,q>0, find lim⁡n→∞ln⁡anna_{n}=pa_{n-1}+qa_{n-2},\ a_{1}>0,\ a_{2}>0,\ p,q>0,\ \text{find } \lim_{ n \to \infty } \frac{\ln a_{n}}{n}