Jan 2, 2010

Continued Fractions - An introduction

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html


You might find the Calculator Continued Fraction Calculator useful in this section.
  1. What is the pattern under the square root signs in the table above: that is, what is the nth term in the series 5,8,13,29,29,40,... ?
    1. What is the next line in the table above for T(11)?
    2. Express the n-th line, that is T(n) as a formula involving square-roots.
  2. T(1) is Phi = ( 1 + √5 )/2.
    1. T(4) = 2 + √5 and also involves √5. Using the Table of Properties of Phi express T(4) as a power of Phi.
    2. T(11) also involves √5. What is T(11)?
      Is it a power of Phi too?
    3. What is the pattern here? Which powers of Phi are also silver means and which silver means are they?
      [Hint: the answer involves the Lucas numbers.]
  3. What powers of Phi are missing in the answer to the previous question? What are their continued fractions?
  4. Express all the powers of Phi in the form (X+Y√5)/2. Find a formula for Phin in terms of the Lucas and Fibonacci numbers.

Continued Fractions and the Fibonacci Numbers

In this section we will take a closer look at the links between continued fractions and the Fibonacci Numbers.

Squared Fibonacci Number Ratios

What is the period of the continued fractions of the following numbers?
  1. 25/9
  2. 64/25
  3. 169/64
You might have noticed that in all the fractions, both the numerator (top) and denominator (bottom) are square numbers (in the sequence 1, 4, 9, 16, 25, 36 ,49, 64,... ). The numbers that are squared are Fibonacci numbers (starting with 0 and 1 we add the latest two numbers to get the next, giving the series 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... ).
The fractions above are the squares of the ratio of successive Fibonacci numbers:
  1. 25/9 = (5/3)2 = (Fib(5)/Fib(4))2
  2. 64/25 = (8/5)2 = (Fib(6)/Fib(5))2
  3. 169/64 = (13/8)2 = (Fib(7)/Fib(6))2
  4. ...
There is a simple pattern in the continued fractions of all the fractions in this series.

What other continued fraction patterns in fractions formed from Fibonacci numbers (and the Lucas Numbers 2, 1, 3, 4, 7, 11, 18, 29, 47, ... ) can you find?

Article: Continued Fractions of Quadratic Fibonacci Ratios Brother Alfred Brousseau in The Fibonacci Quarterly vol 9 (1971) pages 427 - 435.
Article: Continued Fractions of Fibonacci and Lucas Ratios Brother Alfred Brousseau in The Fibonacci Quarterly vol 2 (1964) pages 269 - 276.


A link between The Golden string, Continued Fractions and The Fibonacci Series

Suppose we make the golden sequence into a binary number (base 2) so that its columns are interpreted not as (fractional) powers of 10, but as powers of 2:
0·1011010110 1101011010 1101101011 ...
= 1x2–1 + 0x2–2 + 1x2–3 + 1x2–4 + 0x2–5 + 1x2–6 + ...
It is called the Rabbit Constant.
Expressed as a normal decimal fraction, it is
0·70980 34428 61291 3... .
Its value has been computed to 330 decimal places where our Phi is referred to as tau.

The surprise in store is what happens if we express this number as a continued fraction. It is

[0; 1, 2, 2, 4, 8, 32, 256,...]
These look like powers of 2 and indeed all of the numbers in this continued fraction are powers of two. So which powers are they? Here is the continued fraction with the powers written in:
[0; 20, 21, 21, 22, 23, 25, 28, ..]
Surprise! The powers of two are the Fibonacci numbers!!!
[0; 2F(0), 2F(1), 2F(2), ... , 2F(i), ...]

Perhaps even more remarkably, a discussion on sci.math newsgroup proves a result that Robert Sawyer posted:- that we can replace the base 2 by any real number bigger than 1 and the result is still true!

article A Series and Its Associated Continued Fraction J L Davison, Fibonacci Quarterly vol 63, 1977, pages 29-32.
article A Simple Proof of a Remarkable Continued Fraction Identity P G Anderson, T C Brown, P J-S Shiue Proceeding American Mathematical Society vol 123 (1995), pgs 2005-2009
has a proof that the Rabbit constant is indeed the continued fraction given above.

Two Continued Fractions involving the Fibonacci and the Lucas Numbers

The continued fraction for √5 φ = 5 – √5  = 1.3819660112501051518... is [1;2,1,1,1,1,1,1,1,...]

2
and its convergents are: 1, 3 4 7 11 18 29 , ...

2

3

5

8

13

21
The pattern continues with the Lucas Numbers on the top and the Fibonacci Numbers on the bottom of the convergent's fractions.

Taking the reciprocal of this value, i.e.

Φ  =  2  = 0.72360679774997896964... = [0;1,2,1,1,1,1,1,1,1,1,...]

√5

5 – √5
we get the Fibonacci numbers on the top and the Lucas numbers on the bottom of the convergents: :
1, 2 3 5 8 13 21 , ...

3

4

7

11

18

29

Article: The Strong Law of Small Numbers Richard K Guy in The American Mathematical Monthly, Vol 95, 1988, pages 697-712, Example 14.


Links and References

WWW Links


WWW: Eric Weisstein's page on The Rabbit Constant

WWW: Chaos in Numberland: The secret life of continued fractions Prof John D Barrow, a +Plus magazine online article which, if you have enjoyed this page, will extend your knowledge with more on applications of continued fractions. Some of it is at undergrauate mathematics level.

References to articles and books

articleC. Kimberling, A visual Euclidean algorithm in Mathematics Teacher, vol 76 (1983) pages 108-109.
is an early reference to the excellent Rectangle Jigsaw approach to continued fractions that we explored at the top of this page. An even earlier description of this method is found in chapter IV Fibonacci Numbers and Geometry of:
Book: Fibonacci Numbers, N N Vorob'ev, Birkhauser (2003 translation of the 1951 Russian original).
This slim classic is a translation from the Russian Chisla fibonachchi, Gostekhteoretizdat (1951). This classic contains many of the fundamental Fibonacci and Golden section results and proofs as well as a chapter on continued fractions and their properties.
Book: Introduction to Number Theory with Computing by R B J T Allenby and E Redfern
1989, Edward Arnold publishers, ISBN: 0713136618
is an excellent book on continued fractions and lots of other related and interesting things to do with numbers and suggestions for programming exercises and explorations using your computer.
Book: The Higher Arithmetic by Harold Davenport,
Cambridge University Press, (7th edition) 1999, ISBN: 0521422272
is an enjoyable and readable book about Number Theory which has an excellent chapter on Continued Fractions and proves some of the results we have found above. (More information and you can order it online via the title-link.)
Beware though! We have used [a,b,c,d,...]=X/Y as our concise notation for a continued fraction but Davenport uses [a,b,c,d,..] to mean the numerator only, that is, just the X part of the (ordinary) fraction!
Book: Introduction to the Theory of numbers by G H Hardy and E M Wright
Oxford University Press, (6th edition, 2008), ISBN: 0199219869
is a classic but definitely at mathematics undergraduate level. It takes the reader through some of the fundamental results on continued fractions. Earlier editions do not have an Index, but there is a Web page Index to editions 4 and 5 that you may find useful. This latest edition, the 6th, is revised and has some new material on Elliptic functions too.
Book: Continued Fractions by A Y Khinchin,
This is a Dover book (1997), ISBN: 0 486 69630 8, well produced, slim and cheap, but it is quite formal and abstract, so probably only of interest to serious mathematicians!
Book: Continued fractions (A Popular Survey) Roger F Wheeler, published by The Mathematical Association, 2002.
It is available via the MA website.
This book is a more gentle and systematic introduction, with plenty of illustrative examples and tables.
Three articles on continued fractions with a single repeated digit or a pair of repeated digits or with a single different digit followed by these patterns:
Article: A Limited Arithmetic on Simple Continued Fractions, C T Long and J H Jordan,
Fibonacci Quarterly, Vol 5, 1967, pp 113-128;
Article: A Limited Arithmetic on Simple Continued Fractions - II, C T Long and J H Jordan,
Fibonacci Quarterly, Vol 8, 1970, pp 135-157;
Article: A Limited Arithmetic on Simple Continued Fractions - III, C T Long,
Fibonacci Quarterly, Vol 19, 1981, pp 163-175;


No comments: