interface( warnlevel=0 ): with( laylinalg ): # Text Reference: Sections 5.3 and 4.8 # Wikipedia Reference: Fibonacci Number # Lab 6: The Fibonacci Sequence and the Lucas Sequence # # The purpose of this Lab is to provide an introduction to the Fibonacci sequence, which arises in number theory, applied mathematics, and biology. In the process you will see how useful eigenvalues and eigenvectors can be in understanding the dynamics of difference equations. # # Fibonacci Sequence # The Fibonacci sequence is the sequence of numbers # 0, 1, 1, 2, 3, 5, 8, 13, . . . # You can probably see the pattern: Each number is the sum of the two numbers immediately preceding it. Symbol y[k]; is the k^th; number in the sequence (with y[0] = 0;), called the k^th; Fibonnaci number. # # How can y[k]; be found without just computing the sequence term by term? The answer to this question involves matrix multiplication and eigenvalues. The Fibonacci sequence is governed by the equations # y[k+2]=y[k+1]+y[k], y[0]=0, y[1]=1,; # or, equivalently, # y[k+2]-y[k+1]-y[k] = 0, y[0] = 0, y[1] = 1;. # # Section 4.8 in Lay's textbook 5/E identifies the last equation as a second-order linear difference equation. For reasons which will shortly become apparent, a trivial equation is added to get the following system of equations: # y[k+1] = y[k+1]; # y[k+2] = y[k]+y[k+1]; A := Matrix( 2,2, [[0,1],[1,1]] ): A; # To see how linear algebra applies to this problem, define vector u[k]; = Vector(2, {(1) = y[k], (2) = y[k+1]}); and matrix , where A = Matrix(2, 2, {(1, 1) = 0, (1, 2) = 1, (2, 1) = 1, (2, 2) = 1});. The above system of equations may then be written as the vector-matrix equation u[k+1]; = A u[k];. To find Fibonacci number y[k];, extract the top entry in vector u[k];. The vector u[k]; could be written in terms of u[0]; by noting that by inductive reasoning # u[k]; = A u[k-1]; = A A u[k-2]; = . . . = A^k; u[0]; # # The first goal is to find an easy way to compute A^k;. This is where eigenvalues and eigenvectors enter the picture. # # Problems to be Submitted: # Problem 1. # Define A = Matrix(2, 2, {(1, 1) = 0, (1, 2) = 1, (2, 1) = 1, (2, 2) = 1});. Using Maple, compute A^5; and use it to find vector u[5]; and then find Fibonacci number y[5];. # # Problem 2. # Show that the eigenvalues of matrix A are lambda[1] = (1+sqrt(5))*(1/2); and lambda[2] = (1-sqrt(5))*(1/2); by solving the characteristic equation of A. # Problem 3. # Show that Vector(2, {(1) = -lambda[2], (2) = 1}); and Vector(2, {(1) = -lambda[1], (2) = 1}); are eigenvectors of A corresponding to lambda[1]; and lambda[2]; respectively. You may find it helpful to note that lambda[1]+lambda[2] = 1; and that lambda[1]*lambda[2] = -1;. # Problem 4. # A 2x2 matrix A is defined to be diagonalizable provided it has 2 eigenpairs. Explain why A is diagonalizable, by exhibiting the 2 eigenpairs. # Problem 5. # A diagonalizable matrix A satisfies the equation AP=PD where D is a diagonal matrix of eigenvalues and P is the augmented matrix of corresponding eigenvectors (D and P are not unique). Use the results of Problem 4 to find an invertible matrix P and a diagonal matrix D for which A = P D P^(-1);. # Problem 6. # Use Maple to calculate D^10;, then use it to find A^10= PD^(10);1/P;, vector u[10];, and Fibonacci number y[10];. Confirm your result for y[10]; by writing out the Fibonacci sequence by hand and then consulting Wikipedia. In the solution, explain in detail why A^10= PD^(10);P^(-1).; # Problem 7. # A formula for y[k]; may be derived using the preceding two problems. Use aleady derived expressions for P, D, and A^k; to obtain the formula Ak := 1/sqrt(5) *Matrix( 2,2, [ [ lambda[2]^k*lambda[1], lambda[2]^(k+1)*lambda[1]-lambda[1]^(k+1)*lambda[2] ], [lambda[1]^k-lambda[2]^k, lambda[1]^(k+1)-lambda[2]^(k+1) ] ] ): print( Ak ); # A^k; = 1/sqrt(5); Matrix(2, 2, {(1, 1) = d^k*c, (1, 2) = d^(k+1)*c-c^(k+1)*d, (2, 1) = c^k-d^k, (2, 2) = c^(k+1)-d^(k+1)}); where c = lambda[1] and lambda[1] = (1+sqrt(5))*(1/2);, d=lambda[2]=(1-sqrt(5))/(2).; # # Problem 8. # Use the result of Problem 7 to find vector u[k]; and Fibonacci number y[k];. Again make note of the fact that cd = lambda[1]*lambda[2] = -1;. The answer should be u0 := Vector( 2, [1,1] ): uk := Ak . u0: yk := uk[1]: yk; # y[k]; = 1/sqrt(5); lambda[1]^k-lambda[2]^k; = 1/sqrt(5);((1+sqrt(5))*(1/2))^k-((1-sqrt(5))*(1/2))^k; # Calculate Fibonacci number y[10]; using this formula, and compare your result to that of Problem 6. # Problem 9. # Notice that the second eigenvalue lambda[2]; is less than 1 in absolute value, so term lambda[2]^k; will approach zero as k;approaches infinity. The following approximate equation results for the k^th;Fibonacci number: # y[k]; ~ 1/sqrt(5);((1+sqrt(5))*(1/2))^k; # Use this approximation to approximate y[k+1]/y[k];. # The approximation for y[k+1]/y[k]; which you found in the last question is called the golden ratio, or golden mean. The ancient Greek mathematicians thought that this ratio was the perfect proportion for the rectangle. That the golden mean appears as the limiting ratio for the Fibonacci sequence (which occurs in nature in sunflowers, nautilus shells, and in the branching behavior of plants) makes one wonder about the interconnections between nature, beauty, and number. # # Lucas Sequences # # The above work on the Fibonacci sequence can be generalized to discuss any difference equation of the form # y[k+2] = a*y[k+1]+b*y[k]; # where a; and b; can be any real numbers. A sequence derived from this equation is often called a Lucas sequence, named for French mathematician Edouard Lucas. # Problems to be Submitted: # Problem 10. # Consider the Lucas sequence generated by the difference equation # y[k+2] = 3*y[k+1]-2*y[k]; # with y[0] = 0; and y[1] = 1;. Write out by hand the first seven terms of this sequence and see if you can find the pattern. Then apply eigenanalysis, as was done for the Fiboanacci sequence, to find a formula for y[k];. # Problem 11. # Consider the Lucas sequence generated by the difference equation # y[k+2] = 2*y[k+1]-y[k]; # with y[0] = 0; and y[1] = 1;. Find the pattern by writing out as many terms in the sequence as you need. Will the Fibonacci sequence analysis work in this case? Why or why not? Consult the Wikipedia page on the Lucas Sequence for a solution formula. Therein the following section applies with a=b=S=1 [notation from the Wiki page]: # # # #