Java Reference
In-Depth Information
If we continue for more terms, the ratio appears to converge on a value
slightly greater then 1.618. Assuming f(n)=f(n1) really does converge
to a fixed value as n grows, we can determine what that value must be.
f(n)
f(n 2)
=
f(n 1)
f(n 2)
+
f(n 2)
f(n 2)
! x + 1
For some value x. This follows from the fact that f(n) = f(n 1) +
f(n 2). We divide by f(n 2) to make the second term go away, and
we also get something useful in the first term. Remember that the goal of
such manipulations is to give us an equation that relates f(n) to something
without recursive calls.
For large n, we also observe that:
f(n)
f(n 2)
f(n)
f(n 1)
f(n 1)
f(n 2)
! x
2
=
as n gets big. This comes from multiplying f(n)=f(n 2) by f(n
1)=f(n 1) and rearranging.
If x exists, then x
2
x1 ! 0. Using the quadratic equation, the only
solution greater than one is
1 +
p
5
2
x =
1:618:
This expression also has the name . What does this say about the growth
rate of the Fibonacci sequence?
It is exponential, with f(n) = (
n
).
More precisely, f(n) converges to
n
(1 )
n
p
5
:
14.2.2
Expanding Recurrences
Estimating bounds is effective if you only need an approximation to the answer.
More precise techniques are required to find an exact solution. One approach is
called expanding the recurrence. In this method, the smaller terms on the right
side of the equation are in turn replaced by their definition. This is the expanding
step. These terms are again expanded, and so on, until a full series with no recur-
rence results. This yields a summation, and techniques for solving summations can
then be used. A couple of simple expansions were shown in Section 2.4. A more
complex example is given below.
