Cool Properties
Limit of Ratio:
It is well known that the ratio of two consecutive terms $\frac{F_{n+1}}{F_n}$ of the Fibonacci sequence approaches $\varphi$ as $n$ approaches infinity. This is very easy to show using Binet’s formula:
$$
\begin{eqnarray}
\lim\limits_{n \rightarrow \infty} \frac{F_{n+1}}{F_n} & = & \lim\limits_{n \rightarrow \infty} \frac{\frac{\varphi^{n+1} – (-\varphi)^{-(n+1)}}{\sqrt{5}}}{\frac{\varphi^{n} – (-\varphi)^{-n}}{\sqrt{5}}} \\
& = & \lim\limits_{n \rightarrow \infty} \frac{\varphi^{n+1} – (-\varphi)^{-(n+1)}}{\varphi^{n} – (-\varphi)^{-n}} \\
& = & \lim\limits_{n \rightarrow \infty} \frac{\varphi^{n+1}}{\varphi^{n}} \\
& = & \varphi \\
\end{eqnarray}
$$
It turns out the ratio of any Recurrence of the form $F_n = F_{n-2} + F_{n-1}$ regardless of base conditions will have a ratio that approaches $\varphi$ (assuming the terms are monotonically increasing). In fact, the proof is even easier than the one above that assumes some base conditions.
Suppose we know that $\frac{F_{n+1}}{F_n}$ approaches some value $r$ as $n \rightarrow \infty$. If this is true, $\lim\limits_{n \rightarrow \infty} \frac{F_{n+1}}{F_n} = \lim\limits_{n \rightarrow \infty} \frac{F_{n}}{F_{n-1}}$, and we can assume that $n$ is “$\infty$” in the analysis. Now we just need to use the recurrence relationship.
$$
\begin{eqnarray}
r & = & \frac{F_{n+1}}{F_n} \\
& = & \frac{F_n + F_{n-1}}{F_n} \\
& = & 1 + \frac{F_{n-1}}{F_{n}} \\
& = & 1 + \frac{1}{r} \\
0 & = & r^2 – r – 1 \\
r & = & \frac{1 \pm \sqrt{5}}{2}
\end{eqnarray}
$$
OK, so for the proof to actually be correct, I would have to do limits as $n$ approaches infinity, but I think the point is clear. Now, assuming the terms are monotonically increasing, it’s clear the ratio approaches $\frac{1 + \sqrt{5}}{2} = \varphi$, and notice how no assumptions were made as to the base conditions. This will turn out to be an useful result in some later analysis.
Generating Function:
Generating functions are pretty cool. Essentially, they take some sequence of terms $\{a_0, a_1, \ldots, a_n\}$ to be the coefficients of increasing powers of $x$, making an infinite order polynomial. For small domains of $x$, you can even calculate the value of the polynomial. What is the generating function for the Fibonacci sequence?
$$S(x) = \sum\limits_{n = 0}^{\infty} F_n x^n$$
It turns out this can be represented in a nice, closed form solution:
$$
\begin{eqnarray}
S(x) & = & \sum\limits_{n = 0}^{\infty} F_n x^n \\
& = & F_0 + F_1 x + \sum\limits_{n = 2}^{\infty} F_n x^n \\
& = & F_0 + F_1 x + \sum\limits_{n = 2}^{\infty} \left(F_{n-1} + F_{n-2}\right) x^n \\
& = & F_0 + F_1 x + \sum\limits_{n = 2}^{\infty} F_{n-1} x^n + \sum\limits_{n = 2}^{\infty} F_{n-2} x^n \\
& = & F_0 + F_1 x + \left(F_0 x^0 + x \sum\limits_{n = 2}^{\infty} F_{n-1} x^{n-1} \right) + x^2 \sum\limits_{n = 2}^{\infty} F_{n-2} x^{n-2} \\
& = & 0 + x + x \sum\limits_{n = 0}^{\infty} F_{n} x^{n} + x^2 \sum\limits_{n = 0}^{\infty} F_{n} x^{n} \\
& = & x + x S(x) + x^2 S(x) \\
& = & \frac{x}{1 – x – x^2}
\end{eqnarray}
$$
This is a fairly nice way to represent that sum isn’t it? The radius of convergence is more or less clearly $\frac{1}{\varphi}$ since $\frac{1}{\varphi} = -\varphi$ is a zero of $1 – x – x^2$.
Recursion Tree Properties:
While the recursion method of finding $F_n$ may not be the most efficient (it’s pretty much the least efficient, actually), the whole recursion tree is pretty interesting. Conventionally, since each call to the function usually spawns two more calls, most people (including some teachers I’ve had) would say calculating the $n^{\text{th}}$ Fibonacci number recursively takes $O(2^n)$ time. Now it is correct, that $2^n$ is an upper bound, but I was wondering if I could provide a better upper bound.
Before that, let’s look at a simpler problem: How many leaf nodes should be on the recursion tree? (We can define a leaf node as $F_1$ or $F_0$.)
Clearly, there is only one leaf node when calling $F(1)$ or $F(0)$ (via the definition). Also, it’s clear that $F(2)$ will have two leaf nodes. $F(3)$ will have three leaves, and we can sort of see a pattern emerge. It’s pretty obvious that the $F(n)$ has $F(n-1) + F(n-2)$ leaf nodes. Of course, this is just the Fibonacci sequence with $F_0 = 1$ and $F_1 = 1$ as the base cases. Then, it’s pretty easy to see that in general, the number of leaves on the recursion tree of $F(n)$ is $F(n+1)$.
OK, back to the main problem: How many recursive calls are required for $F(n)$? (Again, start with the same base conditions as above, meaning we’ll stop at $F_1$ and $F_0$. One way to look at this problem is to notice that the number of recursive calls is equivalent to the number of nodes in the recursion tree.)
We can define the number of calls needed for calculating $F_n$ to be some function $C(n)$. Now, let’s say we call $F_n$. This is already one call. Then, we need to call $F_{n-2}$ and $F_{n-1}$. We’ve already defined the number of calls needed for those two as $C(n-2)$ and $C(n-1)$, respectively. Clearly, the following recurrence holds:
$$
\begin{eqnarray}
C(0) & = & 1 \\
C(1) & = & 1 \\
C(n) & = & 1 + C(n-1) + C(n-2)
\end{eqnarray}
$$
The base cases are fairly trivial, as is the derivation of the recurrence relationship. But the recurrence itself is not very informative. It sort of looks like the Fibonacci Recurrence, except for the added $1$. My dad and I spent a part of a bus ride trying to figure out how to solve this. We eventually figured out a way. To solve this recurrence, consider another function, $T(n)$ given by:
$$C(n) = T(n) – 1$$
If we substitute in,
$$
\begin{eqnarray}
T(n) – 1 & = & 1 + T(n-1) – 1 + T(n-2) – 1 \\
T(n) & = & T(n-1) + T(n-2)
\end{eqnarray}
$$
This is sort of nice… $T(n)$ does satisfy the Fibonacci Recurrence. Using $T(n) = C(n) + 1$, it’s pretty clear that $T(n)$ is defined completely as:
$$
\begin{eqnarray}
T(0) & = & 2 \\
T(1) & = & 2 \\
T(n) & = & T(n-1) + T(n-2)
\end{eqnarray}
$$
Figuring out the closed form of $T$ is similar in methodology to that of the Fibonacci function. I won’t go through the derivation, but the end result is:
$$T(n) = \frac{2}{\sqrt{5}} \left( \varphi^{n+1} – (-\varphi)^{-(n+1)} \right)$$
And of course, this means:
$$C(n) = \frac{2}{\sqrt{5}} \left( \varphi^{n+1} – (-\varphi)^{-(n+1)} \right) – 1$$
This, I think, should give the exact number of recursive calls needed. Now earlier I mentioned that many people generally put the upper bound at $O(2^n)$ for the number of calls (which is similar to the time complexity). As we can see from the equation above, however,
$$\lim\limits_{n \rightarrow N} C(n) = \frac{2}{\sqrt{5}} \varphi^{N+1}$$
for large $N$. The complexity could therefore more precisely be bounded at $O(\varphi^n)$ (after getting rid of the constants, including one factor of $\varphi$). Kind of cool, I guess… (and maybe somewhat intuitive). Anyway, that’s about all I want to talk about with regards to Fibonacci Numbers. If you want to read more about Fibonacci Numbers, visit MathWorld or Wikipedia.