M | A | T | H |

2 | 1 | B |

Mathematics Math21b Spring 2017

Linear Algebra and Differential Equations

Exhibit: Liber Abacus

Course Head: Oliver Knill

Office: SciCtr 432

Email: knill@math.harvard.edu

| x(n+1) | | 1 1 | | x(n) | | x(1) | | 1 | | x(n) | = | 1 0 | | x(n-1) |, | x(0) | = | 0 |The eigenvalues are φ=1.61803... and -1/φ. To solve the system, we write the initial condition as a linear combination of the eigenvectors

| 1 | | φ | | -1/φ | | 0 | = ( | 1 | - | 1 | )/ 5then write down the closed form solution^{1/2}

| x(n+1) | | φ | | -1/φ | | x(n) | = (φLooking at the second coordinates gives^{n}| 1 | - (-1/φ)^{n}| 1 | )/ 5^{1/2}

x(n) = [( (1+5In Mathematica^{1/2})/2)^{n}- (1-5^{1/2})/2)^{n}]/5^{1/2}

phi=(1+Sqrt[5])/2; F[n_]:=(phi^n - (-1/phi)^n)/Sqrt[5]; Table[Simplify[F[n]],{n,10}]Now, Mathematica has this already implemented. The same result can be obtained with

Table[Fibonacci[n],{n,10}]We could also program the recursion

G[0]=0; G[1]=1; G[n_]:=G[n-1]+G[n-2]; Table[G[n],{n,10}]Now, you might think, whats the point? If the procedure is already built into the system or can be programmed with recursion of half a line, why do we need the explicit solution? Lets look how long a machine needs to compute the built in Fibonacci number for n=1000000000 or the recursion or then using the F formula above:

First[Timing[Fibonacci[10^9]]]Now, the recursion with G fails with an error "Recursion depth of 1024 exceeded during evaluation". Well, lets increase the recursion limit:

$RecursionLimit=10^9; G[0]=0; G[1]=1; G[n_]:=G[n-1]+G[n-2]; First[Timing[G[10^9]]]If you run it you see it kills the program. One of the ways to segfault Mathematica! What is nifty about the explicit formula is that we can just say that F[1000000000] is equal to (phi^(1000000000) - (-1/phi)^(100000000))/Sqrt[5]. This takes 50 milli seconds:

phi=(1+Sqrt[5])/2; F[n_]:=(phi^n - (-1/phi)^n)/Sqrt[5]; First[Timing[F[10^9]]]However, doing the same command with 10^13 gives an error "Uncaught SystemException returned to top level". The memory resources to handle such large algebraic expression was too large. Folio 139v-140r of the Liber Abbaci. (Biblioteca Nazionale Centrale, Florence, Italy)

Please send questions and comments to knill@math.harvard.edu

Math21b Harvard College Course ID:110989| Oliver Knill | Spring 2017 |
Department of Mathematics |
Faculty of Art and Sciences |
Harvard University,
[Canvas, for admin],
Twitter