Fibonacci Numbers and Binet's Formulausing Linear Algebra

Fibonacci Numbers and Binet's Formula using Linear Algebra April 26, 2021 1 Fibonacci Numbers A sequence {1, 3, 5, 7, 9, 13, . . .}) is a list that never ends (e.g. The Fibonacci Sequence is an exciting sequence discovered almost 1000 years ago. The rst few numbers are: f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 0 1 1 2 3 5 8 13 21 34 ... ... The rule that makes the Fibonacci Sequence is the next number is the sum of the previous two. This kind of rule is sometimes called a recurrence relation. Mathematically, this is written as: fn = fn−1 + fn−2 There is an explicit formula for the n-th Fibonacci number known as 1 fn = √ 5 In the rest of this note, we will use √ !n 1 1+ 5 −√ 2 5 linear algebra to derive Binet's formula: √ !n 1− 5 2 Binet's formula for the Fibonacci numbers. will partial explain where these mysterious numbers in the formula come from. Fibonacci numbers using matrix multiplication This The main tool is to rewrite the and use some tools from linear algebra for simplifying matrix multiplication. 2 Converting the Fibonacci numbers to linear algebra To use the power of linear algebra on the Fibonacci numbers, we dene a sequence of vectors ~v1 , ~v2 . . . two-dimensional Fibonacci that contain the Fibonacci sequence, which we dene as follows:  ~vn = fn  fn+1 The rst few vectors are in this list (compare this to the list of Fibonacci numbers to see the pattern):  ~v0  0 1  ~v1  1 1 Because of the denition of going from one vector ~vn ,  ~vn ~v2  1 2  ~v3  2 3 • The rst component • The second component of ~vn+1 ~vn+1 ~v4  3 5 and the update rule to the next vector of  ~vn+1 is equal to the  ~v5  5 8  ~v6  8 13 fn = fn−1 + fn−2  ~v7  13 21  ~v8  21 34 ... ... for the Fibonacci numbers, the rule for is given by the following two rules: second component is equal to the These two rules can be written down all at once as of ~vn sum of the rst and second component matrix multiplication!  ~vn+1 = 0 1 1 1 1  ~vn of ~vn . The update rule is equivalent to: We can use this update rule a bunch of times to write everything in terms of  the starting point ~v0 = 0 1  the matrix 0 1 1 1  and  . For example for  ~v3 =  =  =  = In general, the formula for powers of ~vn ~v3 we have  0 1 1 1 0 1 1 1 0 1 1 1  0 1 1 1 3 ~v2  0 1 1 1 0 1 1 1  ~v1  0 1  1 1 ~v0 ~v0 is just:  ~vn = 0 1 n  1 1  0 1  We are now really close to Binet's formula! We just need to nd an explicit formula for the matrix power 0 1 1 1 n . 3 Explicit formula for a matrix power  In this section we will nd an explicit for 0 1 n 1 1 . The key to nding the explicit formula for a matrix power is  0 1 to use a special matrix decomposition. It is a fact that the matrix matrices as follows:  0 1 1 1   = 1√ √ 1+ 5 2 " 1√ 1− 5 2 1+ 5 2 0√ 1 1 #" 1− 5 2 0  can be written as a product of three √ −1+ √ 5 2 √ 5 −1− √ 5 2 5 √1 5 −1 √ 5 # Why would anyone write such a nasty looking product?!?! In fact this decomposition is very nice because the and last matrix in this product are inverses of each other:  1√ 1+ 5 1− 5 2 2 √ −1+ √1 √ 5 2 √5 5 1+√ 5 −1 √ 2 5 5 " " 1√ # √ −1+ √ 5 2 √5 1+√ 5 2 5 1√ 1+ 5 2 √1 5 −1 √ 5 # 1√  1− 5 2  1 0 0 1   1 0 0 1  = = For this reason it is more visually convenient to call this matrix  B  and just write: "  √ −1+ √ 5 2 √5 1+√ 5 2 5 1√ 1+ 5 2 √1 5 −1 √ 5 # 1√  = B −1 =B 1− 5 2  0 1 1 1 "  =B 2 √ 1+ 5 2 0 0√ 1− 5 2 # B −1 rst This inverse property of the rst and last matrix means that when you write out the matrix power you get a remarkable simplication. For example:  0 1 2 1 1  0 1 = 1 1 0 1 B =B " =B " =B B 1− 5 2 √ 1+ 5 2 ! # 0√ 0 "  1 1 √ 1+ 5 2 " =  0 1− 5 2 √ 1+ 5 2 0√ B −1 B 1− 5 2 √ 1+ 5 2 0√ #" 1 0 " 0 1 0√ 1− 5 2 √ 1+ 5 2 0√ B −1 # B −1 # 0√ B −1 1− 5 2  0   −1 B √ 2 1− 5 2 The last step works out easily because the middle matrix in our decomposition is a M = BDB −1 diagonal matrices is very easy! This type of decomposition we used, of each other and D are the D −1 # 1− 5 2 0 0 B 1− 5 2 0 √ 1+ 5 2 1− 5 2   √  2 1+ 5 2  =B 0
! # 0√ 0 √ 1+ 5 2 " # 0 0 B # 0√ √ 1+ 5 2 " −1 diagonal matrix. where B and B −1 Multiplying are inverses diagonalizing a matrix. The entries of the diagonal matrix The columns of B are the eigenvectors. Some more details about how to is a diagonal matrix, is called eigenvalues of the matrix. D calculate the matrix and the matrix B are given in the next section. As we've seen here for the Fibonacci numbers, this trick makes it possible to compute the powers of the matrix. The same trick works for  0 1 1 1 n  0 1 1 1  = " = B " =B " =B any power 0 1 1 1 √ 1+ 5 2 0 √ 1+ 5 2  0√  ... # =B   " B √ 1+ 5 2 1− 5 2 √ 1+ 5 2 0√ " B # 1− 5 2  √ n 1+ 5 2  −1 1 0 0 √ n 1− 5 2
B ... B −1   0 1 ... 1 0  B
0 1 # 0√ 0 # 0√ 0 0 1 1 ! B −1 1− 5 2 0  0 1 1− 5 2 √ 1+ 5 2 √ 1+ 5 2 0  B −1 3 B −1 " ... B # 0√ 1− 5 2 0 " ! 0√ 1− 5 2 B −1 # B −1 √ 1+ 5 2 0 0√ 1− 5 2 # ! B −1 So nally we get the explicit formula for the Fibonacci vectors  0 1 1 1   ~vn =  =  = 1√ 1+ 5 2 1− 5 2 1√ 1√ 1+ 5 2 1− 5 2 1√ 1√ 1+ 5 2  0 √ n  B 1− 5 2   √ n  1+ 5 2   −1 as     √ n 1+ 5 2     1− 5 2 √1 5 −1 √ 5  " √ 1− 5 2 n  " 0  0  √ n 1− 5 2 √ n 1+ 5 2  √ n 1− 5 2 n-th 0 1 0 0 Finally we can read o the explicit formula for the exactly ~vn   0 1√ = 0 1 √ n 1+ 5 2 =B  n   √ −1+ √ 5 2 √ 5 −1− √ 5 2 5 √1 5 −1 √ 5 √1 5 −1 √ 5 # 0 1  #   Fibonacci number fn because the rst component of ~vn is fn : fn = rst 1 =√ 5 ~vn √ !n 1+ 5 1 −√ 2 5 component of √ !n 1− 5 2 This is Binet's formula!!! 4 How to nd the decomposition of the matrix In this section I'll show some of the calculations that are needed to get the decomposition which we used to nd Binet's formula:  4.1 0 1 1 1   = 1√ 1+ 5 2 1√ " 1− 5 2 √ 1+ 5 2 0√ #" 1− 5 2 0 √ −1+ √ 5 2 √ 5 −1− √ 5 2 5 √1 5 −1 √ 5 # Disclaimer on Eigenvalues and Eigenvectors Eigenvalues and eigenvectors are a fundemental tool for dealing with matrices! In this section, I'm going to show the calculation you would do to get the matrix we used. However, if you've never seen eigenvalues/eigenvectors before it will probably not make much sense. eigenvalues/eigenvectors You might be interested in watching the 3Blue1Brown video on https://www.youtube.com/watch?v=PFDu9oVAE-g on eigenvectors and eigenvalues to get a more intuitive feel for this before jumping into these calculations. 4.2 Characteristic polynomial and eigenvalues We start by computing the characteristic polynomial of the matrix:  p(λ) = det  = det 0 1 1 1 −λ 1   −λ 1 1−λ 1 0  0 1  = −λ (1 − λ) − 1 = λ2 − λ − 1 We then nd the eigenvalues as the roots of the characteristic polynomial using the quadratic formula: √ √ 1+ 5 1− 5 λ1 = , λ2 = 2 2 4 M − λI We then solve for the eigenvalues by nd the nullspace of 4.3 Nullspace associated to We solve for the vector ~x λ1 in  0 1 1 1 √ ! 1+ 5 1 0 2  −    x1 0 = x2 0 ! √ 1+ 5 x1 = x2 2 ⇐⇒ So x1 = 1, x2 = √ 1+ 5 is a valid eigenvector. 2  Nullspace associated to We solve for the vector ~x  1√ ~e1 = 4.4 1+ 5 2 λ2 in  0 1 1 1 √ ! 1− 5 1 0 2  − x1 = 1, x2 =    x1 0 = x2 0 ! √ 1− 5 x1 = x2 2 √ 1+ 5 is a valid eigenvector. 2  1√ ~e2 = 4.5 !  0 1 ⇐⇒ So !  0 1  1− 5 2 Putting it together  In the basis ~e1 ,~e2 0 1 we have that the matrix for writing a matrix in the basis  0 1 1 1 ~e1 ,~e2 ,   = " 1√ 1+ 5 2 1− 5 2 1√ 1√ 1+ 5 2 In the last step, I've used the formula for a  1√ " 1− 5 2 2×2  =⇒ is diagonal with entries λ1 , λ2 . By the 1√ 1√ change of basis result we have then: 1√  =  1 1 1+ 5 2 a c √ 1+ 5 2 0√ # 0 1− 5 2 √ 1+ 5 2 0√ #" 0 1− 5 2 1+ 5 1− 5 2 2 √ −1+ 5 √1 √ 2 √5 5 1+√ 5 −1 √ 2 5 5 inverse matrix b d 1√ 1− 5 2 −1   1 d −c ad − bc −b a " # √ 1− 5 1 −1 2√ = √ 1 − 5 − 1+2 5 = −1 5 −1 #