From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Fri Apr  4 13:52:42 2008
Date:         Fri, 4 Apr 2008 13:52:20 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191:  Solving the Fibonacci recurrence relation
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191:  Solving the Fibonacci recurrence relation
------------------------------------------------------------------------

Let's try to solve the Fibonacci recurrence relation,
i.e., find a non-recursive formula for the Fibonacci sequence:

	1,1,2,3,5,...

where	f_n = f_(n-1) + f_(n-2)

and	f0 = f1 = 1

------------------------------------------------------------------------

Digression 1:  

The last time I talked about the Fibonacci sequence, I used different
initial conditions:  f0 = 0 and f1 = 1, which I think is what the text
uses.  You can also use f0 = 1 and f1 = 2.  (Or anything else, for that
matter.)  

Different initial conditions will result in different non-recursive
formulas!  I'll return to this later.

------------------------------------------------------------------------

Step 1:  Find the char. eqn. r^2 - c1*r - c2 = 0:

	To do this, we need to find the c1, c2 such that:

		f_n = c1*f_(n-1) + c2*f_(n-2).

	Clearly, c1 = c2 = 1. 

	So, the char eqn is:	r^2 - r - 1 = 0.  

------------------------------------------------------------------------

Digression 2:

This equation is closely related to the "golden ratio", a ratio of
natural numbers that the classical Greeks believed had aesthetic value:
The Parthenon's dimensions are in the golden ratio, and the golden
ratio appears in many other places (such as the dimensions of the
various sizes of index cards!).  

The golden ratio is defined as follows:  Consider this rectangle:

           r       s               Its dimensions are r x (r+s),
     __________________            & I've divided it into 2 smaller
     |           |    |            rectangles, one of which is an
     |           |    |            r x r square, and one of which is
     |           |    |            an r x s rectangle.
  r  |           |    |
     |           |    |            A rectangle is "golden" if
     |___________|____|            its r x s subrectangle is also
                                   golden (sounds recursive, doesn't it?)

That would mean that r+s stands in the same relation to r
as r stands to s; i.e., (r+s)/r = r/s

Cross-multiplying, we get:	r^2 = s(r+s) 
				    = sr + s^2.

Rearranging, we get:	r^2 - sr - s^2 = 0.

To make things simple, suppose s = 1.  Then we get:

	r^2 - r - 1 = 0

But that's the char eqn of the Fibonacci sequence!

------------------------------------------------------------------------

Step 2:	Let's solve that equation, using the quadratic formula:

	r = [1 +/- sqrt(1+4)]/2 = [1 +/- sqrt(5)]/2

------------------------------------------------------------------------

Step 3:	Find @1, @2 such that f_n = @1*r1^n + @2*r2^n

	WOLOG, let r1 = [1 + sqrt(5)]/2
		   r2 = [1 - sqrt(5)]/2

	Using the initial conditions,

		f0 = 1 = @1*r1^0 + @2*r2^0 = @1 + @2

		f1 = 1 = @1*r1^1 + @2*r2^1 
		       = @1*[1 + sqrt(5)]/2 + @2*[1 - sqrt(5)]/2

	Now, I'll let you do the rest of this, because it's too painful
	for me to type, but if you solve these two simultaneous
	equations, you'll get:

		@1 = [1 + sqrt(5)]/2
		@2 = [3 + sqrt(5)]/2

	And so:

		f_n = @1*r1^n + @2*r2^n

		    = ([1 + sqrt(5)]/2)*([1 + sqrt(5)]/2)^n
		      +
		      ([3 + sqrt(5)]/2)*([1 - sqrt(5)]/2)^n

I've shown you this before, but now you know where the square root of 5
comes from!

------------------------------------------------------------------------

Exercises for the reader:

1)	Do the same for initial conditions f0 = 0, f1 = 1
2)	Do the same for initial conditions f0 = 1, f1 = 2

To see an answer for problem (2), look at:

Buck, R.C. (1963),
"Mathematical Induction and Recursive Definitions",
American Mathematical Monthly 70(2) (February): 128-135.
http://www.cse.buffalo.edu/~rapaport/191/S08/Private/buck63-MathIndnRecDefs.pdf

(username=Bill; password=Rapaport) (*)

(*) (This, by the way, answers a previous question that someone asked
     about HW 9's answers ;-)