Math 455.1  •  13 March 2009

The Fibonacci numbers: an example of a recursively defined function

Version 7.02

This notebook shows how to define the Fibonacci numbers recursively in Mathematica.

Defining a function recursively

We give two particular rules and one general rule.

You do not have to say the general rule is for n≥3 (although you could), since Mathematica always tries to use a particular rule it knows before it uses a general rule.

fib[1]=1;
fib[2]=1;
fib[n_]:=fib[n-1]+fib[n-2]

What does Mathematica now know about this function fib?

?fib

Try using the definition:

fib[3]

Now what does Mathematica now know about this function fib?  The same things it knew before: it does not save the value it just calculated for fib[3].

?fib

How does evaluation of a recursive function work?

To see how Mathematica does the recursion, use Trace. (The second argument, fib, to Trace tells Trace only to show expressions involving fib and not things like the calculation of 5-1 as 4.)

Trace[fib[5],fib]

Caching: giving a recursive function a "memory"

We now modify the defintion so as to "cache" the values as soon as they are calculated—to give Mathematica a memory of newly calculated values in the form of additional, particular rules.

(You need not understand the subtleties of just why this is doing what it is doing. Instead, look at what happens.)

Clear[fibonacci]

fibonacci[1]=1;fibonacci[2]=1;
fibonacci[n_]:=fibonacci[n]=fibonacci[n-1]+fibonacci[n-2]

?fibonacci

fibonacci[3]

Now what does Mathematica know about the function fibonacci?

?fibonacci

Notice that Mathematica has indeed added a rule for fibonacci[3] to what it knows about fibonacci.

Why cache? Look at the difference in timings below for the original definition and the definition "with memory":

Timing[fibonacci[30]]

Timing[fib[30]]

Why the significant difference? The reason is that with fib[30], each time it recurses back one step, it has to recalculate all the values prior to that one. With fibonacci[30], Mathematica already has at its ready disposal each of these values ever after they are first calculated.

Finding a closed-form formula for a recursively defined function

This discussion carries out the reasoning in the text.

By the very definition of the sequence of Fibonacci numbers, each Fibonacci number (Subscript[F, n]) beyond (Subscript[F, 1]) and (Subscript[F, 2]) is related to its two immediate predecessors in the sequence by the recurrence relation (Subscript[F, n])=(Subscript[F, n-1])+(Subscript[F, n-2]). But how is each Fibonacci number (Subscript[F, n]) related to its one immediate predecessor (Subscript[F, n-1])? One thing to try to find out is what the ratio (Subscript[F, n])/(Subscript[F, n-1]) is; actually, it's easier to avoid subtracting and write this ratio in the form (Subscript[F, n+1])/(Subscript[F, n]). Carry out an experiment; we'll used the cached form of the definition above:

Table[{n,fibonacci[n+1]/fibonacci[n]},{n,1,5}]//TableForm

That's not very enlightening. Instead, look at the numeric value of the ratios:

Table[{n,N[fibonacci[n+1]/fibonacci[n]]},{n,1,10}]//TableForm

That's getting interesting: it lools like the ratio (Subscript[F, n+1])/(Subscript[F, n]) may be approaching a limit of around 1.618.

If we knew that the ratios (Subscript[F, n+1])/(Subscript[F, n]) did not just approach a constant as n->∞, but in fact that the ratios were constant—
	(Subscript[F, n+1])/(Subscript[F, n])=r
for some constant r, then we could immediately get a closed-form formula for (Subscript[F, n]) in terms of n:
	(Subscript[F, 2])=r (Subscript[F, 1]),
	(Subscript[F, 3])=r (Subscript[F, 2])=r(r (Subscript[F, 1]))=(r^2)(Subscript[F, 1]),
(Subscript[F, 4])=r (Subscript[F, 3])=r((r^2)(Subscript[F, 1]))=(r^3)(Subscript[F, 1]),
⋮
(Subscript[F, n])=(r^(n-1))(Subscript[F, 1]).

But the preceding cannot be correct, since in fact the ratios are not actually constant. For example,
	(Subscript[F, 2])/(Subscript[F, 1])=1/1=1 but (Subscript[F, 3])/(Subscript[F, 2])=2/1=2.

Nonetheless, let's try to see what would happen if the sequence of (Subscript[F, n])'s were like such a geometric progression. Form an arbitrary geometric progression
	(Subscript[G, 1])=c, (Subscript[G, 2])=q c, (Subscript[G, 3])=(q^2)c, …
and, in general,
	(Subscript[G, n])=(q^(n-1))c		(n=1,2,…)		(*)
where both the initial value c and the constant ration q are yet to be determined.

If the sequence of (Subscript[G, n])'s is very much alike the sequence of (Subscript[F, n])'s, then perhaps the (Subscript[G, n])'s also satisfy the same recurrence relation as the Fibonacci numbers:
	(Subscript[G, n+1])=(Subscript[G, n])+(Subscript[G, n-1]).				(**)

You should have found that there are actually two different solutions fo q to make the recurrence relation (**) hold for the sequence of (Subscript[G, n])'s, namely:
	q=((1+(Sqrt[5]))/2),    q=((1-(Sqrt[5]))/2).

OK, now in each case what is c? We want the (Subscript[G, n])'s to be like the (Subscript[F, n])'s, so let's try to make the initial values (Subscript[G, 1]) and (Subscript[G, 2]) to be the same as the initial values (Subscript[F, 1])=1 and (Subscript[F, 2])=1, respectively.

That seems like a dead-end. But wait! all is not lost. Maybe (Subscript[F, n]) is not simply an actual geometric progression—actually, we already know it cannot be—but perhaps some kind of combination of two different (but related) geometric progressions. In fact, we have two different geometric progressions already lurking here: one for q=((1+(Sqrt[5]))/2) and the other for q=((1+(Sqrt[5]))/2). Give these geometric progressions different names:
	(Subscript[G, n])=c (((((1+(Sqrt[5]))/2)))^n),   (Subscript[G, n])'=c (((((1-(Sqrt[5]))/2)))^n).

Exercise. Let (Subscript[H, n])=(Subscript[G, n])-(Subscript[G, n])'.
	(a) Show that the sequence of (Subscript[H, n])'s satisfies the same recurrence relation as the sequence of Fibonacci numbers.
	(b) Find the value of c for which (Subscript[H, n])=(Subscript[F, n]) for all n. (Hint: In particular, you want (Subscript[H, 1])=(Subscript[F, 1]).
	(c) Now use mathematical induction to show that, in fact, the sequences of the (Subscript[H, n])'s and the (Subscript[F, n])'s are the same.

In (b) you should have found c=1/(Sqrt[5]). This means that the Fibonacci numbers are given by the closed-form formula:

That seems amazing at first—that the Fibonacci numbers, which are of course positive integers, are nevertheless given by a formula involving (Sqrt[5]).