The Fibonacci sequence and matrix diagonalization
Names:

Upload completed labs to Moodle by 1pm Friday: https://lms.ats.amherst.edu/mod/assign/view.php?id=314050

The sequence of numbers defined by

(Subscript[a, 0])=0

(Subscript[a, 1])=1

(Subscript[a, n])=(Subscript[a, n-1])+(Subscript[a, n-2])   for  n=2,3,4,...

is called the Fibonacci sequence. This sequence was described by the Italian mathematician Leonardo Fibonacci in the 13th century to model the growth of rabbit populations (see page 369 of the textbook) and is named after him, although the sequence actually appeared centuries earlier in Indian mathematics. This sequence appears in nature in various ways, for instance, in the arrangement of leaves on a stem, shape of an uncurling fern, the pattern on a pine cone (see the poster in Mudd 014). 

Exercise 1. Find the first 10 numbers in the Fibonacci sequence ((Subscript[a, 0]) through (Subscript[a, 9])).

Finding the first few Fibonacci numbers is pretty easy, but the numbers grow exponentially as n increases. What if we want to find (Subscript[a, 100])? That’s not so easy -- it’s a very large number. Let’s apply diagonalization to analyze the Fibonacci sequence (treated as a dynamical system), and thereby find a straightforward way to calculate numbers far out in the sequence like (Subscript[a, 100]).

Exercise 2. Rewrite the recursive definition for (Subscript[a, n]) in matrix-vector form (Subscript[u, n+1])=A(Subscript[u, n]) where (Subscript[u, 0])=(({{(Subscript[a, 1])}, {(Subscript[a, 0])}}))=(({{1}, {0}})) and (Subscript[u, n])=(({{(Subscript[a, n+1])}, {(Subscript[a, n])}})). That is, if (({{(Subscript[a, n+1])}, {(Subscript[a, n])}}))=A(({{(Subscript[a, n])}, {(Subscript[a, n-1])}})), what is the 2x2 matrix A? Hint: substitute the original definition in for (Subscript[a, n+1]).

Exercise 3. Based on what we know about discrete dynamical systems of this form, (Subscript[u, n])=(A^n)(Subscript[u, 0]) where (Subscript[u, n])=(({{(Subscript[a, n+1])}, {(Subscript[a, n])}})). Calculate the vectors (Subscript[u, 1]) through (Subscript[u, 4]) using the formula (Subscript[u, n])=(A^n)(Subscript[u, 0]). You may use the command MatrixPower[A,n] in Mathematica to find (A^n). Vectors can be input into Mathematica using curly braces, like (Subscript[u, 0])={1,0}.

Calculating large powers of A is no better than using the original formula, so we want to do something slicker. A nice application of matrix diagonalization is to find a formula for large powers of a matrix that is easy to understand and compute.

Exercise 4. Find the eigenvalues and eigenvectors of A (you can use Eigensystem[A]//MatrixForm), and use them to determine matrices P and D such that A=PD(P^(-1)). (The larger eigenvalue is the golden ratio.) Note: you will have to call the diagonal matrix something other than D in Mathematica, for instance, B.

Exercise 5.  What is a simpler form for (D^n) ? That is, taking powers of a diagonal matrix can be simplified to taking powers of ...

Exercise 6. We can now generate a formula for powers of A via (A^n)=P(D^n)(P^(-1)). Enter this formula into Mathematica to obtain an expression for powers of A. You can use Inverse[P] to calculate the matrix inverse of P if you wish.

Exercise 7. Multiply your formula for (A^n) times the initial vector (Subscript[u, 0])={1,0} to obtain (Subscript[u, n]). The 2nd entry will equal (Subscript[a, n]). State the formula this gives you for (Subscript[a, n]).

Exercise 8. Substitute n=100 into your formula for (Subscript[a, n]) to calculate (Subscript[a, 100]). (To actually compute a  numerical value, you need to use the command N[...]. See you if you can adjust the precision/accuracy to determine the exact number.)