Tags

, ,

fareypoincaremovie

Farey tessellation in complex plane

In fact, the matrix formulation of Fibonacci numbers mentioned before can be generalized to represent any 2-D matrix and, by way of continued fractions, any real number – not just the golden mean. This post is inspired from David Austin’s AMS feature column and draws on Phillipe Flajolet’s beautiful survey on continued fractions to set the stage for a future post on Diophantine approximation.

Every matrix A of determinant one with non-negative integer coefficients will have a unique factorization…corresponding to a continued fraction expansion.” [1]

A = \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right] = U^{\alpha_0}L^{\alpha_1}U^{\alpha_2}L^{\alpha_3}... \\ where \ U = \left[ \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array} \right], \\ \ L = \left[ \begin{array}{cc} 1 & 0 \\ 1 & 1 \end{array} \right], \ and \\ \frac{b}{d} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \dotsb}}}

 The Fibonacci numbers can be derived as

\left[ \begin{array}{cc} F_{n-1} & F_{n} \\ F_{n-2} & F_{n-1} \end{array} \right] = ULULUL... \\ \phi(n) = \frac{F_{n}}{F_{n-1}} = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \dotsb}}}

Of course, both the factorization series and the fraction terminate for finite values of n i.e. rational approximations of the golden mean. Already this formulation can be used to calculate the n-th Fibonacci number in log(n) steps.

While “every positive rational number appears in the Stern-Brocot tree,” [2] such factorization also represents a specific path in the tree whose nodes provide the optimal rational approximation to a real number within a given error.

References

[1] P. Flajolet, B. Vallee, and I. Vardi. Continued fractions from Euclid to present day. Preprint, March 2000.
[2] D. Austin. Trees, Teeth, and Time: The mathematics of clock making. AMS Feature Column, December 2008.

Advertisements