Answer Happy

The Fibonacci numbers are an infinite sequence of integers For F1, F2, F3, ........ in which the integers are defined inductively as follows: Fo = 0, F, = 1, and if n 2 1, then Fn+1 = F, + Fn-1 Using this definition the first few Fibonacci numbers after F, are as follows: F2 = F, + F = 1, F3 - F + F, -2, F4 = F3 + F2 - 3, F = F + F3 = 5, F = Fs + F2 = 8, F, = F + Fs = 13, F = F, + F6-21, F, = Fg + F7 = 34, F10 = Fg + Fg = 55. The problem with computing Fibonacci numbers using this inductive definition is that you need to know the values of all the Fibonacci numbers that precede a number in the sequence in order to compute it. For example, if you wanted to compute F100, then you would first need to compute all 100 Fibonacci numbers F. through Fgg before you could finally compute F100. This is very impractical. What is needed is a closed formula for Fn, meaning a formula from which F, could be directly computed from the subscript n. If you had such a closed formula, then, for example, F100 could be directly computed from it using n = 100 without having to know the first 100 Fibonacci numbers. Such a closed formula can be found and proved to be correct using linear algebra. This project leads you through the process of discovering and proving such a closed formula. First we need to do some initial setting up before beginning this process. Define another infinite sequence of integers inductively E, E , E2, E3, ........ as follows: For each integer n 2 0, we define E,- Ft 1. Thus E, -F, - 1, E - F - 1, E2 - F3 = 2, etc. Note that the sequences E, and F, satisfy the following two linear equations for n 2 1: En-1 + F1 = E. En-1 + OF-1 = F. These equations follow from the definitions of the sequences E, and F. Now define matrix A = -( .) and for each integer n 2 0, column vector x, =
In particular note that Xo = We introduce these, because now the system of two linear equations given above can be expressed using matrix algebra as: Axn-1 = x, for n 2 1. (*) Finally, for use later, we define two real numbers q and y as Ф 1+V5 Q = .1; and W= 1-15 2 2
THE PROJECT - PART II: Let a and b be two integers. A sequence of Generalized Fibonacci numbers is an infinite sequence of integers Go, G, G2, G3, ........ in which the integers are defined inductively as follows: Go = 0, G = 1, and if n 2 1, then Gn+1 = a, + bgn-1- As an example, if we let a = 2 and b = 3, then we get the following sequence of Generalized Fibonacci numbers: Go = 0, G, = 1, G2 = 26, + 3G, = 2, G3 = 262 + 3G, = 7, G4 = 263 + 3G2 = 20, etc. Computing Generalized Fibonacci numbers involves the same difficulty as computing the Fibonacci numbers themselves. In Part II you are going to derive another closed formula to compute the Generalized Fibonacci numbers in terms of the numbers a and b. First define another infinite sequence of integers inductively E., E,, E2, E3, ........ as follows: For each integer n 2 0, we define E, = Gn+1. En For each integer n 20, column vector x, = G. Note that x = 0-0 NOTE: In doing this part you are leaving the numbers a and b as variables. You are not replacing a and b by specific numbers as in the example above. 1) Find a 2x2 matrix B so that for n 21 BX 1 = X = X, is also This matrix B is analogous to the matrix A in Part I. The matrix equation BX-1 analogous to the matrix equation () in Part II. As in Part I, we can prove again by mathematical induction that for all n 2 1, B"X, = X. We will assume this result is true, so you do not need to prove it here. 2) Now proceed through the same steps as you did in Part 1; find the two eigenvalues of B (expressed in terms of a and b), then find an eigenvector of B for each of your eigenvalues (again expressed in terms of a and b), then express the vector Xo = as a linear combination of your En eigenvectors, and finally express the vector x, = --- as a linear combination of the eigenvectors. After you have done these steps you should be able to read off a closed formula for G, in terms of the numbers a and b. 3) As a way of checking the correctness of your formula, let a = 2 and b = 3. Use your closed formula for G, to compute Go, G, G2 and G3. If you use a calculator, then round off answers to the nearest integer. Your answers should match the values in the example at the top of the page.