Closed Form Continued Fraction Expansions of Special Quadratic Irrationals

Dan Fishman^{1} Mathematics Department

Princeton University Princeton, NJ 08544

May 19, 2003

1E-mail: dfishman@math.princeton.edu

Abstract

We explore methods for determining the underlying structure of certain classes of continued fractions . The goal is to develop closed form expressions for the continued fractions of many quadratic irrationals. Consider a finite difference equation satisfying:

• G_{n+1} = a_{n}G_{n} + b_{n}G_{n−1}.

• a_{n} = m, and b_{n} = l for all n, where m, l ∈ ℕ

note: m = l = 1 gives the Fibonacci numbers.

Let G_{n} denote the n^{th} term of the sequence, and let τ denote the lim_{n→∞} \frac{G_{n+1}}{G_{n}}. We derive formulas for \frac{G_{n}}{G_{n−k}} for certain m, l; in particular, these allow us to determine closed form continued fraction expansions of τ^{k} for any positive integer k.

Contents

1 Background on Continued Fractions 3 1.1 An Introduction to Continued Fractions . . . . . . . . . . . . . . 3 1.2 Known Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Some Previous Techniques . . . . . . . . . . . . . . . . . . . . . 6 1.4 The Simple Model . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Background on Fibonacci Numbers 11 2.1 Brief History on Fibonacci Numbers . . . . . . . . . . . . . . . . 11 2.2 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 The Continued Fraction Expansion of Ratios of Fibonacci k-Neighbours 14 3.1 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 First Efforts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 A Proof in Full Generality For Fibonacci Ratios . . . . . . . . . . 17 3.4 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 The General Difference Equation 20 4.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5 More Closed Form Expressions 25 5.1 Case 1: l = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2 Case 2: l = −1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3 Case 3: l divides m . . . . . . . . . . . . . . . . . . . . . . . . . 28

6 On Repeating Blocks of Length Greater Than 2 31 6.1 Repeating Blocks of Length 3 . . . . . . . . . . . . . . . . . . . 31

7 For Those Who Come After 36 A Tables: Continued Fraction Expansions of Ratios of Fibonacci

k-Neighbours 38

B Tables: Length of the Repeating Blocks of the Powers of τ, where τ has the form: [\overline{a_{0}, a_{1}, …, a_{n}}] 43

C Tables: Length of the Repeating Blocks of the Powers of τ, where τ has the form: [a_{0}, \overline{a_{1}, …, a_{n}}] 46

Chapter 1

Background on Continued Fractions

1.1 An Introduction to Continued Fractions

Every real number α can be represented in the form:

a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+ \frac{1}{...}}}}

We call such a representation a continued fraction . We can simplify this representation by restricting the a_{i}, called the partial quotients, to be positive integers. To construct the continued fraction , one must simply let:

a_{0} = [α]

a_{1} = \frac{1}{α − [α]}

⋮

In order to simplify the notation, the usual convention will be used:

α = [a_{0}, a_{1}, a_{2}, ...]

Continued fractions turn out to be convenient representations of numbers since they provide the best approximation to a given number. The greatest problem with continued fractions is that such a representation does not lend itself to ordinary manipulations with any kind of ease. Although integer shifts are easy to handle, rational shifts, or even integer multiples, are not easy to explicitly determine. For example, doubling a continued fraction may require a complicated evaluation.

Say α = \frac{7914}{1913} = [4,7,3,3,6,4]

Then 2α = \frac{15828}{1913} = [8,3,1,1,1,6,3,8] The expansions only become messier as the number of terms in the continued fraction expansion increases.

Therefore, it would be useful to develop a good understanding of the fundamental underlying structure of continued fractions , if in fact such a structure even exists. Although this is somewhat of a daunting task, my goal is to develop closed form expressions for some simple families, for which such a structure appears to exist, and then try to generalize the findings.

1.2 Known Results

Before we proceed, we will need a few basic results We begin with a simple correspondence outlined in [AvP1]:

Lemma 1.2.1.

( \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}a_{1} & 1 \\ 1 & 0 \end{matrix} ) … ( \begin{matrix}a_{n} & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}p_{n} & p_{n−1} \\ q_{n} & q_{n−1} \end{matrix} ) ∀n ∈ ℕ

⇕
\frac{p_{n}}{q_{n}} = [a_{0}, a_{1}, …, a_{n}]  (1.1)

The proof from [AvP1] follows by induction on n. Since this proof demonstrates the connection between continued fractions and 2-dimensional matrices, which is often explored in the literature, I will include it here.

Proof: The base case, n = 0, is trivial. Now, left multiply the first line of 1.1 by:

( \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} )^{−1} = ( \begin{matrix}0 & 1 \\ 1 & −a_{0} \end{matrix} )

Then LHS of 1.1 = ( \begin{matrix}a_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}a_{2} & 1 \\ 1 & 0 \end{matrix} ) … ( \begin{matrix}a_{k} & 1 \\ 1 & 0 \end{matrix} )

And RHS = ( \begin{matrix}q_{k} & q_{k−1} \\ p_{k} − a_{0}q_{k} & p_{k−1} − a_{0}q_{k−1} \end{matrix} )

By the inductive hypothesis, the correspondence holds for n < k terms, and so we have:

\frac{q_{k}}{p_{k} − a_{0}q_{k}} = [a_{1}, …, a_{k}] ⇒ \frac{1}{\frac{p_{k}}{q_{k}} − a_{0}} = [a_{1}, …, a_{k}]  (1.2)

⇒ \frac{p_{k}}{q_{k}} − a_{0} = \frac{1}{[a_{1}, …, a_{k}]} ⇒ \frac{p_{k}}{q_{k}} = [a_{0}, a_{1}, …, a_{k}]

Q.E.D.

Remark 1.2.2. It is convenient here to note that trivial matrix operations yield:

( \begin{matrix}x & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}y & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}x + y & 1 \\ 1 & 0 \end{matrix} )

⇒ [..., x, 0, y, ...] = [..., x + y, ...]

We now introduce a relevant lemma that describes when we can expect the continued fraction of a given real number to be finite.

Lemma 1.2.3. A continued fraction expansion of α is finite if and only if the number α is a rational number. Furthermore, if α is a quadratic algebraic number, then its continued fraction expansion is periodic. (This last part is known as Langrange’s Theorem).

Proof: see [Class Notes: 7.2 Uniqueness of Continued Fraction Expansions and 8.2 Periodic Continued Fractions ]

As one can imagine, we call \frac{p_{n}}{q_{n}} the n^{th} convergent of α, since as n gets larger, more terms are added and the ratio \frac{p_{n}}{q_{n}} converges to α.

From our correspondence in Lemma 1.2.1 we easily deduce that:

p_{0} = a_{0}, p_{1} = a_{0}a_{1} + 1  (1.3)
q_{0} = 1, q_{1} = a_{0}

and in general:

( \begin{matrix}p_{k} & p_{k−1} \\ q_{k} & q_{k−1} \end{matrix} ) = ( \begin{matrix}p_{k} & p_{k−1} \\ q_{k} & q_{k−1} \end{matrix} ) ( \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} )

⇒ ( \begin{matrix}p_{k} & p_{k−1} \\ q_{k} & q_{k−1} \end{matrix} ) = ( \begin{matrix}c_{k}p_{k−1} + p_{k−2} & p_{k−1} \\ c_{k}q_{k−1} + q_{k−2} & q_{k−1} \end{matrix} )

⇒ p_{k} = c_{k}p_{k−1} + p_{k−2}, q_{k} = c_{k}q_{k−1} + q_{k−2}

A nice relation bewtween convergents is the following lemma [Class Notes: Ch. 5, Observation 5.2.8]:

Lemma 1.2.4.

p_{n}q_{n−1} − p_{n−1}q_{n} = (−1)^{n−1}

Proof: We can prove this using the correspondence in lemma 1.2.1 From elementary linear algebra, we see that the determinant of the RHS = p_{n}q_{n−1}−p_{n−1}q_{n}. Also since det(AB)=det(A)det(B), and the determinant of all matrices in the product on the LHS have determinant of (−1), the determinant of LHS = (−1)^{n+1}.

Q.E.D.

Another nice feature of the Correspondence that we will use later is the symmetry of the matrices on the LHS.

Define A_{i} = ( \begin{matrix}a_{i} & 1 \\ 1 & 0 \end{matrix} ). Then A_{i} = A_{i}^{T} ∀i.

Since (A_{0}A_{1} … A_{n})^{T} = A_{n}^{T} … A_{1}^{T} A_{0}^{T} = A_{n} … A_{1}A_{0} the above and 1.2.1 imply

that this is equal to ( \begin{matrix}p_{n} & p_{n−1} \\ q_{n} & q_{n−1} \end{matrix} )^{T} ⇒ ( \begin{matrix}p_{n} & q_{n} \\ p_{n−1} & q_{n−1} \end{matrix} ).

1.3 Some Previous Techniques

In this section, I will provide the reader with some background on the types of techniques that have been employed to develop closed form expansions of continued fractions of various quadratic irrationals, or quadratic surds.

Definition 1.3.1. (from [mathworld.com]) An irrational number of the form:

\frac{P ± \sqrt{D}}{Q} where P, Q ∈ ℤ and D is some non-square integer,

is called a quadratic surd (also known as a quadratic irrational number).

These numbers are the most interesting since they lead to periodic expansions, as determined by Lagrange’s theorem. Therefore, they provide a good basis for experimentation.

We begin with the work of Alfred van der Poorten from the Macquarie University in Australia. In a paper on continued fractions of a given symmetric period (see [AvP2]), van der Poorten discovers the structure of a certain family of quadratic surds.

He begins with a look at the solutions to Pell’s Equation:

X^{2} − DY^{2} = ±1

where D ∈ ℕ, and not a square.

In [AvP2], he proves that this has solutions in non-zero integers (X, Y). This fact is then used to show that \sqrt{D} has a periodic continued fraction expansion, with a unique structure. The following is van der Poorten’s derivation, from [AvP1] and [AvP2].

Definition 1.3.2. A matrix U is called unimodular if U = (u_{ij}) where u_{ij} ∈ ℤ and det(U) = ±1.

Lemma 1.3.3. (From [AvP2] Proposition 3)

An unimodular matrix U = ( \begin{matrix}a & b \\ c & d \end{matrix} ) such that a, b, c, d ∈ ℤ\\{0\} and a ≥ b, c

has a unique deomposition ( \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}a_{1} & 1 \\ 1 & 0 \end{matrix} ) … ( \begin{matrix}a_{n} & 1 \\ 1 & 0 \end{matrix} ) where a_{0}, …, a_{n} ∈

ℕ.

Remark 1.3.4. One can use the above lemma to verify our initial observation that any real number can be expressed as a continued fraction . Clearly, any real number can be approximated by a sequence of rationals \{\frac{p_{n}}{q_{n}} \}. We can then form a

unimodular matrix of the form ( \begin{matrix}p_{n} & p_{n−1} \\ q_{n} & q_{n−1} \end{matrix} ). The result then follows easily from

1.2.1.

These results are now used to determine the structure for continued fractions of the form β_{1} = \sqrt{D} where D ∈ ℕ, not square and β_{2} = \frac{1+\sqrt{D}}{2}, where D ≡ 1(mod 4) and again D ∈ ℕ, not square.

Now, set M := ( \begin{matrix}X & DY \\ Y & X \end{matrix} ) andJ := ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ), so that det(M) defines

Pell’s equation, and det(J) = −1. If we take the product MJ, Poorten shows (X, Y) can be chosen so that this product MJ is unimodular, and can therefore be decomposed into some product:

( \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}a_{1} & 1 \\ 1 & 0 \end{matrix} ) … ( \begin{matrix}a_{r} & 1 \\ 1 & 0 \end{matrix} )

Since M and J are both symmetric, so is their product. And so an earlier observation shows that a_{0}, a_{1}, ....., a_{r} is a palindrome.

Now, consider some real number δ that has the following repeated Continued Fraction :

δ = [a_{0}, \overline{a_{1}, a_{2}, ..., a_{r−1}, 2a_{r}}]

where a_{0}, ...., a_{r} are chosen as in the continued fraction of MJ. By symmetry, a_{r} = a_{0}. And so we can rewrite delta “in non-periodic” form as:

δ = [a_{0}, a_{1}, a_{2}, ..., a_{r−1}, 2a_{0} + δ − a_{0}]

Now using the correspondence from 1.2.1,

LHS ⇔ ( \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}a_{1} & 1 \\ 1 & 0 \end{matrix} ) … ( \begin{matrix}a_{r} − 1 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}2a_{0} − a_{0} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}δ & 1 \\ 1 & 0 \end{matrix} )

(1.4)

⇒ MJ ∗ J ∗ ( \begin{matrix}δ & 1 \\ 1 & 0 \end{matrix} )

Using J^{2} = I,

⇒ ( \begin{matrix}X & DY \\ Y & X \end{matrix} ) ( \begin{matrix}δ & 1 \\ 1 & 0 \end{matrix} )

⇒ ( \begin{matrix}δX + DY & X \\ δY + X & Y \end{matrix} )  (1.5)

Referring back to the Correspondence 1.2.1, we see that 1.5 implies that:

δ = \frac{δX + DY}{δY + X}

Now, by hypothesis X and Y are non-zero. Furthermore, δY + X ≠ 0 since that would imply δ = \frac{X}{Y}, but δ has a periodic, and therefore infinite, continued fraction expanison, so δ cannot be rational. Therefore, we can multiply through by δY +X

⇒ δ^{2}Y + δX = δX + DY ⇒ δ^{2} = D

And so we see that \sqrt{D} has a Continued Fraction of the form:

δ = [a_{0}, \overline{a_{1}, a_{2}, ..., a_{r−1}, 2a_{0}}]

Note: Earlier we had restricted ourselves to numbers of the form β_{1} and β_{2}. This choice was made since these are the only conditions under which the conditions in Proposition 3 of [AvP2] hold.

The above derivation gives the structure for δ = β_{1}. A similar approach (see [AvP2]) can be used to derive the structure for δ = β_{2}. In this case, it turns out that:

δ = [a_{0}, \overline{a_{1}, a_{2}, ..., a_{r−1}, 2a_{0} − 1}]  (1.6)

So in general, if we take γ ∈ {β_{1}, β_{2}}, then

δ = [a_{0}, \overline{a_{1}, a_{2}, ..., a_{r−1}, 2a_{0} − (γ + γ̄})]

where (γ + γ̄) = \{ \begin{matrix}\sqrt{D} + (−\sqrt{D}) = 0 : & γ = β_{1} \\ (\frac{1+\sqrt{D}}{2}) + (\frac{1−\sqrt{D}}{2}) = 1 : & γ = β_{2} \end{matrix}

We see that van der Poorten and was able to determine the structure of certain types of numbers. He went on to examine the fractional parts of the periods of the continued fractions that satisfy Diophantine equations similar to Pell’s Equation. However, while it is nice to predict the shape of the continued fraction, it would be incredibly useful to be able to predict the length of the repeating block. Van der Poorten’s results do not seem to address this. Therefore, it is my goal to bring a new approach that attempts to determine how special classes of continued fractions behave.

Another technique that shows great progress in manipulating continued fractions comes from an unfinished paper of Bill Gosper (see [BG]). In this paper, Gosper develops a set of algorithms for finding closed form expressions of simple functions of a given quadratic irrational, as well as for more complicated functions combining quadratic irrationals. The paper addresses the need for finding a nice way of adding and multiplying the continued fractions of quadratic surds. The basic technique employed is an analog of Euclid’s algorithm. This operation is carried out using two-dimensional arrays in the simple cases, and then requires added dimensions when considering functions of two or more quadratic irrationals. Such algorithms, while incredibly useful for many practical applications, do not really reveal the nature of the underlying structure in closed form in an accessible manner. This is precisely where I attempt to make some headway.

1.4 The Simple Model

We begin our study with the most simple continued fraction one can imagine. Take a_{i} = 1 for all i. What is our α? Well, α = [1, 1, 1, ...]. We then try to approximate α with its continued fraction convergents, p_{n} = a_{n}p_{n−1} + p_{n−2}. Since a_{n} = 1 for all n, it is clear that:

p_{n} = p_{n−1} + p_{n−2}.
q_{n} = q_{n−1} + q_{n−2}.  (1.7)

Furthermore, since p_{1} = a_{1}a_{0} + 1 = 2, and q_{0} = q_{1} = 1, we see that q_{2} = q_{1} + q_{0} = 2. So we have that p_{2} = q_{1} + q_{0}. In general, we have:

p_{n} = q_{n} + q_{n−1} = q_{n+1} or q_{n} = p_{n−1}.

Therefore, we see that the convergents to α all have the form \frac{p_{n}}{q_{n}} = \frac{p_{n}}{p_{n−1}} If we can find a sequence of integers (p_{n}) that satisfy the rules:

• p_{n} = p_{n−1} + p_{n−2}

• p_{0} = p_{1} = 1

Then

α = lim_{n→∞} \frac{p_{n}}{p_{n−1}}

This sequence, as you should have guessed, is the Fibonacci sequence.

Background on Fibonacci Numbers

2.1 Brief History on Fibonacci Numbers

In 1202, Leonardo Pisano, known as Fibonacci, posed the following puzzle in his book Liber Abaci:

“A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month, each pair begets a new pair which, from the start of the second month on, becomes productive.” [OR]

The solution to the more general problem, where one year is replaced with any number of months, has become known as the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, ...  (2.1)

where each successive term is the sum of the previous two. The sequence is probably the simplest form of a general difference equation:

J_{n} = m_{1}J_{n−1} + m_{2}J_{n−2} + ... + m_{n}J_{0}  (2.2)

where m_{1} = m_{2} = 1 and m_{i} = 0 for i > 2

The Fibonacci sequence, F_{n}, has wonderful applications in almost every area of mathematics.

2.2 Basic Properties

Here are listed some basic properties that will be needed in the paper: Clearly,

Property 2.2.1. F_{n} = F_{n−1} + F_{n−2}

Property 2.2.2. lim_{n→∞} \frac{F_{n}}{F_{n−1}} = \frac{1+\sqrt{5}}{2}

Proof: First, note that: \frac{F_{n}}{F_{n−1}} = \frac{F_{n−1}+F_{n−2}}{F_{n−1}} Let lim_{n→∞} \frac{F_{n}}{F_{n−1}} = x Then we have x = 1 + \frac{1}{x} ⇒ x^{2} − x − 1 = 0 Solving for x using the quadratic formula yields x = \frac{1±\sqrt{5}}{2}

Q.E.D.

A less obvious result, however, is that the n^{th} Fibonacci term can be expressed in the so-called Binet Form as follows:

Property 2.2.3. F_{n} = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n} − (\frac{1+\sqrt{5}}{2})^{n}]

This can be proven inductively.(See [BH] p.21) However, the proof of a more general form will be provided in a later section. (See proposition 4.1.2)

Property 2.2.4. F_{n−2}F_{n} − (F_{n−1})^{2} = (−1)^{n−1}

To see this, note from Lemma 1.2.4:

p_{n}q_{n−1} − p_{n−1}q_{n} = (−1)^{n−1}.

We have already seen that q_{n} = p_{n−1}. So replacing, p_{n} with F_{n} and q_{n} with F_{n−1}, the result follows.

Now, I introduce some notation: If n varies, we write F_{n} to mean the n^{th} Fibonacci term for any n. If k is a fixed constant, we write f_{k} to mean the k^{th} Fibonacci term.

We use this notation in the following:

Property 2.2.5. F_{n} = f_{k+1}F_{n−k} + f_{k}F_{n−k−1}

The Proof of this formula will also wait until the more general form. (See proposition 4.1.4)

We will now use these properties to try and derive closed form continued fraction expressions of a small class of numbers.

The Continued Fraction Expansion of Ratios of Fibonacci k-Neighbours

We begin this chapter with a definition:

Definition 3.0.6. Given a seqence of numbers {x_{n}}, any two numbers t-spacings apart are called t-neighbours (or t-nbrs). That is, x_{n} and x_{n±k} are called k-nbrs.

3.1 Experimental Results

Mathematica was used to generate the continued fraction expansions for several different combinations of Fibonacci terms. We started with the knowledge that as n → ∞, the continued fraction of r_{n} = \frac{F_{n}}{F_{n}−1} ⟶ [1,1,1,1,1,1...]. In the experimental section, we looked for patterns in the ratios of k-neighbour Fibonacci terms for different values of k. Attached in Appendix A are charts with results for k=3,4,and 5.

For k=2, the result is trivial since F_{n} = F_{n−1} + F_{n−2} ⇒ \frac{F_{n}}{F_{n−2}} = 1 + \frac{F_{n−1}}{F_{n−2}} . As n approaches ∞, \frac{F_{n−1}}{F_{n−2}} = \frac{F_{n}}{F_{n−1}} . From this, we easily deduce that:

lim_{n→∞} \frac{F_{n}}{F_{n−2}} = [2, 1, 1, 1, 1, ...]

With k=3, however, the result is not so obvious. From property 2.2.5 we note that F_{n} = f_{3}F_{n−2} + f_{2}F_{n−3} = 2F_{n−2} + F_{n−3}.

⇒ \frac{F_{n}}{F_{n−3}} = 1 + 2\frac{F_{n−2}}{F_{n−3}}

As we have already seen, multiplying a continued fraction by a non-unit can be messy. Of course, for special values of a_{i} the product is easily determined. In general, however, this continued fraction for \frac{F_{n}}{F_{n−3}} is not easily determined from that of \frac{F_{n}}{F_{n−1}} .

The Experimental results do, nonetheless, reveal definite patterns for almost all k. In general,with k fixed, the first few terms of the continued fractions are the same for all n. It is only the last few terms that change. Furthermore, the experimental evidence suggests that the last few terms in the continued fraction expansion repeat themselves for all ratios k-spaces apart. For the remainder of this paper, this phenomenon will be reffered to as k-spaced periodic (or t-spaced periodic in general). This holds for all tested values of k. Also, the values of the first terms: a_{0}, a_{1}, ..., a_{n}, depend on k.

By looking at the experimental results, there seems to be two different patterns that develop. When k is odd, the first few terms in the continued fraction tend to be a fixed number. When k is even, the first few terms alternate between some fixed constant dependent on k, and the digit one. Furthermore, the leading term a_{0} is the sum of these two alternating terms.

For example, for k=4, the first few terms of the continued fraction for large values of n are: [6, 1, 5, 1, 5, 1, ...]

While for k=3, the first few terms are: [4, 4, 4, 4, .....]

These results hold for all k tested (k<10).

Can these results be generalized? The answer to this question turns out to be a cautious yes! The method is developed in subsequent chapters.

3.2 First Efforts

The original technique developed to determine the closed form expression of thecontinued fractions for a given ratio of Fibonacci k-neighbours was one of brute force. For the first few values of k, we worked backwards from the experimental results. Fibonacci terms were manipulated to arrive at the known results. This was done for k=3,4,5,6.

For example, take the case k=3. Looking at Appendix A, the continued fraction expansions of \frac{F_{n}}{F_{n−3}} have the form [4,4,....ρ] where ρ is:

3 if n = 1(mod3)

5 if n = 2(mod3)
4 if n = 0(mod3)

The continued fraction expansion, for all n appears to follow the pattern:

\frac{F_{n}}{F_{n−3}} = 4 + _{\frac{1}{\frac{Fn−3}{F_{n−6}}}}

Working with this hypothesis, we then used property 2.2.1 to reach the result observed experimentally in the following way:

\frac{F_{n}}{F_{n−3}} = \frac{F_{n−1} + F_{n−2}}{F_{n−3}}

= \frac{2F_{n−2} + F_{n−3}}{F_{n−3}}

= 1 + 2\frac{F_{n−2}}{F_{n−3}}

= 1 + \frac{2F_{n−3} + 2F_{n−4}}{F_{n−3}}

= 3 + 2\frac{F_{n−4}}{F_{n−3}}

= 3 + \frac{F_{n−4} + F_{n−3} − F_{n−5}}{F_{n−3}}

= 4 + \frac{F_{n−4} − F_{n−5}}{F_{n−3}}

= 4 + \frac{F_{n−6}}{F_{n−3}}

= 4 + \frac{1}{\frac{F_{n−3}}{F_{n−6}}}

And so the experimental results were confirmed by design.

However, there were two issues with this technique. First, the method was dependent on the experimental results, and thus needed refinement if the goal of reaching a more general proof would in fact be realized. Second, the patterns that developed in the proofs seemed so overwhelming that there had to be some more efficient way to solve the general question for all values of k. Therefore, we analyzed the patterns to develop a more efficient technique.

One pattern that became clear was that the behaviour of the continued fraction depends on the parity of k. The initial attempt was to prove a general statement for the odd values and even values separately. After completing this task, it became clear that a general solution that holds for all k could be derived from a single proof. This proof is the one that will be provided here, since it is the most polished.

3.3 A Proof in Full Generality For Fibonacci Ratios

Given a ratio of k-neighbours in the Fibonacci sequence, what is its continued fraction expansion?

\frac{F_{n}}{F_{n−k}} = \frac{f_{k+1}F_{n−k} + f_{k}F_{n−k−1}}{F_{n−k}}

= f_{k+1} + f_{k} \frac{F_{n−k−1}}{F_{n−k}}

= f_{k+1} + \frac{f_{k−1}F_{n−k−1} + f_{k−2}F_{n−k−1}}{F_{n−k}}

= f_{k+1} + \frac{(f_{k−1}F_{n−k−1} + f_{k−1}F_{n−k−2}) + f_{k−2}F_{n−k−1} − f_{k−1}F_{n−k−2}}{F_{n−k}}

= f_{k+1} + \frac{f_{k−1}F_{n−k}}{F_{n−k}} + \frac{f_{k−2}F_{n−k−1} − f_{k−1}F_{n−k−2}}{F_{n−k}}

= (f_{k+1} + f_{k−1}) + \frac{f_{k−2}F_{n−k−1} − f_{k−1}F_{n−k−2}}{F_{n−k}}  (3.1)

Note: F_{n−k−1} = f_{k}F_{n−k−k} + f_{k−1}F_{n−k−k−1} And F_{n−k−2} = f_{k−1}F_{n−k−k−1} + f_{k−2}F_{n−k−k−2} So Equation 3.1 reduces to

(f_{k+1}+f_{k−1})+\frac{f_{k−2}(f_{k}F_{n−2k} + f_{k−1}F_{n−2k−1}) − f_{k−1}(f_{k−1}F_{n−2k} + f_{k−2}F_{n−2k−1})}{F_{n−k}}

Combining like terms gives:

(f_{k+1} + f_{k−1}) + \frac{f_{k−2}(f_{k}F_{n−2k}) − f_{k−1}(f_{k−1}F_{n−2k})}{F_{n−k}}

Simplifying further:

(f_{k+1} + f_{k−1}) + \frac{F_{n−2k}[f_{k−2}f_{k} − (f_{k−1})^{2}]}{F_{n−k}}

But from property 2.2.4,

f_{k−2}f_{k} − (f_{k−1})^{2} = (−1)^{k−1}

And so

\frac{F_{n}}{F_{n−k}} = (f_{k+1} + f_{k−1}) + \frac{F_{n−2k}(−1)^{k−1}}{F_{n−k}}

Or

\frac{F_{n}}{F_{n−k}} = (f_{k+1} + f_{k−1}) + \frac{(−1)^{k−1}}{\frac{F_{n−k}}{F_{n−2k}}}  (3.2)

Now, if k is odd, then (−1)^{k−1} = 1 and so Equation 3.2 becomes

\frac{F_{n}}{F_{n−k}} = (f_{k+1} + f_{k−1}) + \frac{1}{\frac{F_{n−k}}{F_{n−2k}}}  (3.3)

If k is even, then (−1)^{k−1} = −1 and so Equation 3.2 becomes

\frac{F_{n}}{F_{n−k}} = (f_{k+1} + f_{k−1}) + \frac{−1}{\frac{F_{n−k}}{F_{n−2k}}}  (3.4)

Then we must manipulate further, so that Equation 3.4 becomes

\frac{F_{n}}{F_{n−k}} = (f_{k+1} + f_{k−1} − 1) + 1 − \frac{1}{\frac{F_{n−k}}{F_{n−2k}}}

Now,

1 − \frac{1}{\frac{F_{n−2k}}{F_{n−k}}} = \frac{F_{n−k} − F_{n−2k}}{F_{n−k}}

= \frac{1}{\frac{F_{n−k}}{F_{n−k}−F_{n−2k}}}

= \frac{1}{1 + \frac{F_{n−2k}}{F_{n−k}−F_{n−2k}}}

= \frac{1}{1 + _{\frac{1}{\frac{F_{n−k}−F_{n−2k}}{F_{n−2k}}}}}

= \frac{1}{1 + _{\frac{1}{\frac{F_{n−k}}{F_{n−2k}} −1}}}

3.4 Analysis

The results that we just derived reflect exactly what we observe in the experimental data. In the first place, we see that for all k (even and odd), the continued fraction expansions of the ratio of k-nbrs is k-spaced periodic.

In the case of k odd,

\frac{F_{n}}{F_{n−k}} = [f_{k+1} + f_{k−1}, \frac{F_{n−k}}{F_{n−2k}} ]  (3.5)

This shows that the a_{0} term will be: f_{k+1} + f_{k−1}, and that the succeeding terms are determined by the ratio of the k-neighbours exactly k spacings earlier, thus confirming our observations.

In the case of k even,

\frac{F_{n}}{F_{n−k}} = [f_{k+1} + f_{k−1} − 1, 1, \frac{F_{n−k}}{F_{n−2k}} − 1]  (3.6)

which, again, exhibits the same k-spaced periodicity. Also, the observation that the sequence (f_{k+1}+f_{k−1}−1, 1) repeats is confirmed, as is the fact that the leading term (f_{k+1} + f_{k−1} − 1) is the sum of 1 and [\frac{F_{n−k}}{F_{n−2k}}] = (f_{k+1} + f_{k−1} − 1) − 1. So the results with this simple family work out perfectly!

Since the ratio of consecutive Fibonacci terms approaches the golden ratio, we can apply the techniques we have just developed to find nice closed form expressions for any power of the golden ratio.

(\frac{1 ± \sqrt{5}}{2})^{k} = lim_{n→∞} (\frac{F_{n}}{F_{n−1}} ∗ \frac{F_{n−1}}{F_{n−2}} ∗ … ∗ \frac{F_{n−k+1}}{F_{n−k}} ) = lim_{n→∞} \frac{F_{n}}{F_{n−k}} (3.7)

For large powers k, of the golden ratio, all one must do is find the first k continued fractions, and then use the closed form expressions in either 3.5 if k is odd, or 3.6 if k is even.

The General Difference Equation

Now that we have found closed form expressions of the continued fraction expansion of a small class of numbers (all integral powers of the golden mean), one wonders whether the same techniques can be applied to more general difference equations.

First, it is useful to note that the Fibonacci sequence with f_{1} = f_{2} = 1, is not the only sequence that can be used in the above. In fact, any equation that satisfies F_{n} = F_{n−1} + F_{n−2}, no matter what the choice of intial values, will lead to the same result. Of course, we choose the inital conditions for convenience, so that they match the convergents, p_{n} and q_{n} in the continued fraction of α = [1, 1, ..,]

4.1 Basic Properties

Let us look at a general difference equation of the form:

G_{n} = mG_{n−1} + lG_{n−2}  (4.1)

With the initial conditions: G_{0} = 0, G_{1} = 1.

We try to apply the technique used in the Fibonacci sequence case. The first step will be to verify whether or not the properties 2.2.2 through 2.2.5 hold (or if we can find some equivalent statement.)

Property 4.1.1. lim_{n→∞} \frac{G_{n}}{G_{n−1}} = \frac{m±\sqrt{m^{2}+4l}}{2}

Proof: As with the Fibonacci sequence, let lim_{n→∞} \frac{F_{n}}{F_{n−1}} = τ

then we have τ = m + \frac{l}{τ} or τ^{2} − mτ − l = 0

solving for τ using the quadratic formula yields \frac{m±\sqrt{m^{2}+4l}}{2}

The general difference equation has an equivalent Binet form:

Proposition 4.1.2. (See [DR] p.187) G_{n} = \frac{1}{\sqrt{m^{2}+4l}}[(\frac{m+\sqrt{m^{2}+4l}}{2})^{n}−(\frac{m−\sqrt{m^{2}+4l}}{2})^{n}]

Proof: (By Induction) First, we test the base case. Let n=1. Then clearly

G_{1} = \frac{1}{\sqrt{m^{2}+4l}}[(\frac{m+\sqrt{m^{2}+4l}}{2}) − (\frac{m−\sqrt{m^{2}+4l}}{2})] = \frac{2\sqrt{m^{2}+4l}}{2\sqrt{m^{2}+4l}} = 1

as desired.

Now, assume it holds for G_{k} and G_{k−1}.

Let α_{1} = \frac{m + \sqrt{m^{2} + 4l}}{2} and α_{2} = \frac{m − \sqrt{m^{2} + 4l}}{2}  (4.2)
and let C_{1} = \frac{1}{\sqrt{m^{2} + 4l}} , C_{2} = −C_{1}  (4.3)

Substituting in appropriately gives:

G_{k+1} = mG_{k} + lG_{k−1}
= mC_{1}[(α_{1})^{k} − (α_{2})^{k}] + lC_{1}[(α_{1})^{k−1} − (α_{2})^{k−1}]
= C_{1}[m(α_{1})^{k} + l(α_{1})^{k−1} − m(α_{2})^{k} + l(α_{2})^{k−1}]
= C_{1}[(α_{1})^{k−1}(m(α_{1}) + l) − (α_{2})^{k−1}(m(α_{2}) + l)]  (4.4)

Now, note that:

m(α_{1}) + l

= m(\frac{m+\sqrt{m^{2}+4l}}{2}) + l = ^{\frac{m^{2}+m(\sqrt{m^{2}+4l})+2l}{2}} = ^{\frac{2m^{2}+2m(\sqrt{m^{2}+4l})+4l}{4}} = (\frac{m+\sqrt{m^{2}+4l}}{2})^{2}

= (α_{1})^{2}

And similarly:

m(α_{2}) + l

= m(\frac{m−\sqrt{m^{2}+4l}}{2}) + l = ^{\frac{m^{2}−m(\sqrt{m^{2}+4l})+2l}{2}} = ^{\frac{2m^{2}−2m(\sqrt{m^{2}+4l})+4l}{4}} = (\frac{m−\sqrt{m^{2}+4l}}{2})^{2}

= (α_{2})^{2}

So that Equation 4.4 reduces to:

= C_{1}[(α_{1})^{k−1}(α_{1})^{2} − (α_{2})^{k−1}(α_{2})^{2}]

= C_{1}[(α_{1})^{k+1} − (α_{2})^{k+1}]

= \frac{1}{\sqrt{m^{2} + 4l}}((\frac{m + \sqrt{m^{2} + 4l}}{2})^{k+1} − (\frac{m − \sqrt{m^{2} + 4l}}{2})^{k+1})

And so the result holds.

Q.E.D

Now to see the equivalent of 2.2.4 Proposition 4.1.3. G_{n−2}G_{n} − (G_{n−1})^{2} = (−1)^{n−1} ∗ l^{k−2}

Proof: Again using the substitutions from 4.2 and 4.3 with the Binet Forms. LHS = (C_{1}α_{1}^{k−2} + C_{2}α_{2}^{k−2}) (C_{1}α_{1}^{k} + C_{2}α_{2}^{k}) − (C_{1}α_{1}^{k−1} + C_{2}α_{2}^{k−1})^{2}

recall C_{2} = −C_{1}. Then

LHS = (C_{1}^{2})[(α_{1}^{k−2} − α_{2}^{k−2})(α_{1}^{k} − α_{2}^{k}) − (α_{1}^{k−1}α_{2}^{k−1})]

= C_{1}^{2}[(α_{1}^{2k−2} − α_{1}^{k}α_{2}^{k−2} − α_{1}^{k−2} − α_{2}^{k} + α_{2}^{2k−2}) − (α_{1}^{2k−2} + α_{1}^{k−1}α_{2}^{k−1} + α_{2}^{k−2})]

= C_{1}^{2}[−α_{1}^{k−2}α_{2}^{k−2}(α_{1}^{2} + α_{2}^{2}) + 2(α_{1}α_{2})^{k−2}]

Now,

α_{1}α_{2} = \frac{m + \sqrt{m^{2} + 4l}}{2} \frac{m − \sqrt{m^{2} + 4l}}{2} = \frac{m^{2} − (m^{2} + 4l)}{4} = −l  (4.5)

So we get

LHS = C_{1}^{2}[−(−l)^{k−2}(α_{1}^{2} + α_{2}^{2}) + 2(−l)^{k−1}]

= (−1)^{k−1} ∗ l^{k−2} ∗ C_{1}^{2}[(α_{1}^{2} + α_{2}^{2}) + 2l]  (4.6)

substituting back in for C_{1}, α_{1}, α_{2} yields:

(−1)^{k−1} ∗ l^{k−2} ∗ \frac{1}{m^{2} + 4l}(\frac{m^{2} − \sqrt{m^{2} + 4l} + 2l}{2} + \frac{m^{2} + \sqrt{m^{2} + 4l} + 2l}{2} + 2)

= (−1)^{k−1} ∗ l^{k−2}(\frac{m^{2} + 4l}{m^{2} + 4l})

= (−1)^{k−1} ∗ l^{k−2}  (4.7)

We see that this reduces to ±1 if and only if l= ±1. This result shows as that if we restrict l to be ±1, our techniques for determining the closed form expression of the continued fraction expansion is valid up to this point!

Let us now verify the last property. .

Proposition 4.1.4. G_{n} = g_{k+1}G_{n−k} + lg_{k}G_{n−k−1}

Again, we use the substitutions from 4.2 and 4.3

G_{n} = C_{1}α_{1}^{n} + C_{2}α_{2}^{n}

Let us express G_{n} in terms of any two previous consecutive terms. In matrix form we write:

( \begin{matrix}G_{n−k} \\ G_{n−k−1} \end{matrix} ) = ( \begin{matrix}α_{1}^{n−k} & α_{2}^{n−k} \\ α_{1}^{n−k−1} & α_{2}^{n−k−1} \end{matrix} ) ( \begin{matrix}C_{1} \\ C_{2} \end{matrix} )  (4.8)

( \begin{matrix}C_{1} \\ C_{2} \end{matrix} ) = ( \begin{matrix}α_{1}^{n−k} & α_{2}^{n−k} \\ α_{1}^{n−k−1} & α_{2}^{n−k−1} \end{matrix} )^{−1} ( \begin{matrix}G_{n−k} \\ G_{n−k−1} \end{matrix} )

By Cramer’s Rule,

RHS = \frac{1}{α_{1}^{n−k}α_{2}^{n−k−1} − α_{1}^{n−k−1}α_{2}^{n−k}} ( \begin{matrix}α_{2}^{n−k−1} & −α_{2}^{n−k} \\ −α_{1}^{n−k−1} & α_{1}^{n−k} \end{matrix} ) ( \begin{matrix}G_{n−k} \\ G_{n−k−1} \end{matrix} )

= \frac{1}{α_{1}^{n−k−1}α_{2}^{n−k−1}(α_{1} − α_{2})} ( \begin{matrix}G_{n−k}α_{2}^{n−k−1} & −G_{n−k−1}α_{2}^{n−k} \\ −G_{n−k}α_{1}^{n−k−1} & G_{n−k−1}α_{1}^{n−k} \end{matrix} )

⇒ C_{1} = \frac{G_{n−k}}{α_{1}^{n−k−1}(α_{1}−α_{2})} − \frac{G_{n−k−1}α_{2}}{α_{1}^{n−k−1}(α_{1}−α_{2})} , C_{2} = \frac{−G_{n−k}}{α_{2}^{n−k−1}(α_{1}−α_{2})} + \frac{G_{n−k−1}α_{1}}{α_{2}^{n−k−1}(α_{1}−α_{2})}

Plugging into G_{n} = C_{1}α_{1}^{n} + C_{2}α_{2}^{n} gives:

G_{n} = \frac{(G_{n−k} − G_{n−k−1}α_{2})α_{1}^{n}}{α_{1}^{n−k−1}(α_{1} − α_{2})} + \frac{(−G_{n−k} + G_{n−k−1}α_{1})α_{2}^{n}}{α_{2}^{n−k−1}(α_{1} − α_{2})}

= \frac{α_{1}^{k+1}}{α_{1} − α_{2}} (G_{n−k} − α_{2}G_{n−k−1}) + \frac{α_{2}^{k+1}}{α_{1} − α_{2}} (−G_{n−k} + α_{1}G_{n−k−1})

= G_{n−k} (\frac{1}{α_{1} − α_{2}} (α_{1}^{k+1} − α_{2}^{k+1})) + G_{n−k−1} (\frac{1}{α_{1} − α_{2}} (−α_{2}α_{1}^{k+1} + α_{1}α_{2}^{k+1}))

Now recall from Equation 4.5 that α_{1}α_{2} = −l Furthermore,

α_{1} − α_{2} = \frac{m + \sqrt{m^{2} + 4l} − m + \sqrt{m^{2} + 4l}}{2} = \sqrt{m^{2} + 4l}

So that Equation 4.9 becomes

G_{n−k} (\frac{1}{\sqrt{m^{2} + 4l}}(α_{1}^{k+1} − α_{2}^{k+1})) + G_{n−k−1} (\frac{1}{\sqrt{m^{2} + 4l}}(lα_{1}^{k} − lα_{2}^{k}))

= g_{k+1}G_{n−k} + lg_{k}G_{n−k−1}  (4.9)

as desired.

Q.E.D.

Here, we note that if, l=1, then we may apply the very same technique used in the Fibonacci case. We will see precisely how this works in the next section.

More Closed Form Expressions

In this chapter, we will use the technique developed in section 4.1 to find the closed form continued fraction expressions for powers of any number of the form: \frac{m±\sqrt{m^{2}+4l}}{2} where m, l ∈ ℕ.

If we take the difference equation: G_{n} = mG_{n−1} + lG_{n−2} Then, by the same method applied to the Fibonacci sequence yields,

lim_{n→∞} \frac{G_{n}}{G_{n−1}} = \frac{m ± \sqrt{m^{2} + 4l}}{2}  (5.1)

Can we find closed form expressions for continued fraction expansions for the powers of these limits? In the case of the golden ratio, we have already seen that this can be achieved by determining the continued fraction expansion of the ratio of \frac{G_{n}}{G_{n−k}}. Applying the technique from Chapter 3 to \frac{G_{n}}{G_{n−k}} gives the following: From Proposition 4.1.4: G_{n} = g_{k+1}G_{n−k} + lg_{k}G_{n−k−1}

⇒ \frac{G_{n}}{G_{n−k}} = \frac{g_{k+1}G_{n−k} + lg_{k}G_{n−k−1}}{G_{n−k}}

RHS = g_{k+1} + lg_{k} \frac{G_{n−k−1}}{G_{n−k}}

= g_{k+1} + l ∗ \frac{mg_{k−1}G_{n−k−1} + lg_{k−2}G_{n−k−1}}{G_{n−k}}

= g_{k+1} + l ∗ \frac{(mg_{k−1}G_{n−k−1} + lg_{k−1}G_{n−k−2}) + lg_{k−2}G_{n−k−1} − lg_{k−1}G_{n−k−2}}{G_{n−k}}

= g_{k+1} + l ∗ \frac{g_{k−1}G_{n−k}}{G_{n−k}} + l\frac{lg_{k−2}G_{n−k−1} − lg_{k−1}G_{n−k−2}}{G_{n−k}}

= (g_{k+1} + lg_{k−1}) + l^{2} ∗ \frac{g_{k−2}G_{n−k−1} − g_{k−1}G_{n−k−2}}{G_{n−k}}  (5.2)

Note: From proposition 4.1.4, G_{n−k−1} = g_{k}G_{n−k−k} + lg_{k−1}G_{n−k−k−1} And G_{n−k−2} = g_{k−1}G_{n−k−k−1} + lg_{k−2}G_{n−k−k−2} So Equation 5.2 reduces to

(g_{k+1}+lg_{k−1})+l^{2}∗\frac{g_{k−2}(g_{k}G_{n−2k} + lg_{k−1}G_{n−2k−1}) − g_{k−1}(g_{k−1}G_{n−2k} + lg_{k−2}G_{n−2k−1})}{G_{n−k}}

= (g_{k+1} + lg_{k−1}) + l^{2} ∗ \frac{g_{k−2}g_{k}G_{n−2k} − g_{k−1}g_{k−1}G_{n−2k}}{G_{n−k}}

= (g_{k+1} + lg_{k−1}) + l^{2} ∗ \frac{G_{n−2k}(g_{k−2}g_{k} − (g_{k−1})^{2})}{G_{n−k}}

From proposition 4.1.3,

g_{k−2}g_{k} − (g_{k−1})^{2} = (−1)^{k−1}l^{k−2}
⇒ \frac{G_{n}}{G_{n−k}} = (g_{k+1} + lg_{k−1}) + \frac{G_{n−2k}l^{k}(−1)^{k−1}}{G_{n−k}}  (5.3)

5.1 Case 1: l = 1

Consider the case with l = 1. That is, the difference equations of the form:

G_{n} = mG_{n−1} + G_{n−2}  (5.4)

They are associated with all numbers of the form: τ = \frac{m±\sqrt{m^{2}+4}}{2} Setting l = 1 in 5.3, we see that this is precisely what we derived in 3.2! And so it follows that our technique used in chapter 4 can be applied successfully when l = 1. We are thus now able to determine explicitly the continued fraction expansion of all quadratic irrational numbers τ of the form: \frac{m+\sqrt{m^{2}+4}}{2} where m ∈ ℕ and for any positive, integral power of τ.

Remark 5.1.1. One nice feature of continued fractions is that if one knows the continued fraction expansion of some number α, then the continued fraction expanison of α^{−}1 follows immediately. To see this, suppose α = [a_{0}, a_{1}, ..., a_{n}]. Then α^{−}1 = [0, a_{0}, a_{1}, ..., a_{n}].

(Note:From the above remark and the observation that we can easily find all continued fraction for positive powers of τ, we conclude that the negative powers of τ follow trivially.)

As in the case of the Fibonacci sequence, we see that simplifying expression 5.3 will yield a result exhibiting k-spaced periodicty. That is, the only change from the Fibonacci case is a factor of l in one of the terms in the first partial quotient.

5.2 Case 2: l = −1

Now consider the case where l = −1, i.e. the difference equations of the form:

G_{n} = mG_{n−1} − G_{n−2}

Of course, we will have to choose our intial points such that no number in the sequence is negative.

Setting l = −1 in 5.3, we see that we get:

\frac{G_{n}}{G_{n−k}} = (g_{k+1} + g_{k−1}) + (−1)^{k−1}(−1)^{k} \frac{G_{n−2k}}{G_{n−k}}

⇒ \frac{G_{n}}{G_{n−k}} = (g_{k+1} + g_{k−1}) + (−1)^{2k−1} \frac{G_{n−2k}}{G_{n−k}}

And since (−1)^{2k−1} = (−1) ∀k ∈ ℕ, we do not have the ambiguity that we saw in the previous cases. That is, for all k:

\frac{G_{n}}{G_{n−k}} = (g_{k+1} + g_{k−1}) − \frac{G_{n−2k}}{G_{n−k}}  (5.5)

This is exactly what we saw in 3.4! So all quadratic surds of the form: τ = \frac{m+\sqrt{m^{2}−4}}{2} and their powers have continued fraction Expansions of the form:

τ^{k} = (g_{k+1} − g_{k−1} − 1) + \frac{1}{1 + \frac{1}{τ^{k}−1}}

Which clearly determines a continued fraction with repeating block of length 2 of the form:

τ = [g_{k+1} − g_{k−1} − 1, \overline{1, (g_{k−1} − g_{k−1} − 2})]

So far, we have shown that if l = ±1, then we can determine the continued fraction expansions of the limit. It would be nice if we could extend our results further.

We begin with the general case from 5.3.

τ = (g_{k+1} + lg_{k−1}) + \frac{l^{k}(−1)^{k−1}}{τ}  (5.6)

And so we divide into two cases depending on the parity of k.

With k even:

τ^{k} = (g_{k+1} + lg_{k−1}) − \frac{l^{k}}{τ^{k}}  (5.7)
⇒ τ^{2k} = (g_{k+1} + lg_{k−1}) ∗ τ^{k} − l^{k}

And so by the quadratic formula:

τ^{k} = ^{\frac{(g_{k+1}+lg_{k−1})+\sqrt{(g_{k+1}+lg_{k−1})^{2}−4l^{k}}}{2}}

Similarly, with k odd:

τ^{k} = ^{\frac{(g_{k+1}+lg_{k−1})+\sqrt{(g_{k+1}+lg_{k−1})^{2}+4l^{k}}}{2}}

We can therefore deduce the powers of τ from the the sequence of terms generated by its associated difference equation. (Even in cases when we cannot find nice closed form expressions for the Continued Fractions of the powers of τ)

So now that we have covered all such τ’s of this form, can we extend our techniquefurther yet?

5.3 Case 3: l divides m

Suppose we consider the difference equations of the form:

G_{n} = (d ∗ l)G_{n−1} + lG_{n−2}whered, l ∈ ℕ  (5.8)

Then the associated τ is of the form:

τ = ^{\frac{(d∗l)+\sqrt{(d∗l)^{2}+4l}}{2}}

From our genearal form 5.3, we have:

\frac{G_{n}}{G_{n−k}} = (g_{k+1} + lg_{k−1}) + l^{k}(−1)^{k−1} \frac{G_{n−2k}}{G_{n−k}}  (5.9)

Now, based on our experimental data, we conjecture that τ has a predictable closed form continued fraction expansion. Let us derive this explicitly. We start with setting k=1 in 5.9 Then:

\frac{G_{n}}{G_{n−1}} = (g_{2} + lg_{0}) + l\frac{G_{n−2}}{G_{n−1}}  (5.10)

Now, g_{0} = 0 and g_{1} = 1 by construction. Then g_{2} = (d ∗ l)g_{1} + lg_{0} = (d ∗ l) So we have

\frac{G_{n}}{G_{n−1}} = (d ∗ l) + l\frac{G_{n−2}}{G_{n−1}}  (5.11)

Then:

RHS = (d ∗ l) + \frac{1}{\frac{G_{n−1}}{lG_{n−2}}}

⇒ (d ∗ l) + \frac{1}{\frac{((d∗l)G_{n−2}+lG_{n−3}}{lG_{n−2}}}

⇒ (d ∗ l) + \frac{1}{(d) + _{\frac{1}{\frac{G_{n−2}}{G_{n−3}}}}}

Now taking the lim_{n→∞} to get

τ = (d ∗ l) + \frac{1}{(d) + \frac{1}{τ}}  (5.12)

And therefore τ = [\overline{dl, d}] ⇔ [\overline{m, \frac{m}{l}}]

This confirms our hypothesis. The continued fraction expansion of the difference equations that satisfy l divides m has a well-determined continued fraction .

Caution: this derivation only works with k=1. Therefore, although we extend the results, we do not learn anything about the powers of these τ in this case.

One useful observation is that the ratio of terms in the sequence generated by the difference equations of the type 5.8 is 2-spaced periodic in the sense defined in section 3.1. Experimental data suggests that the powers of τ exhibit some sort of t-spaced periodicity. However, the values of t do not appear to be predictable. A pattern that appears to hold for all values tested, was that for the continued fraction of τ^{k}, t = k ∗2^{s}, where s is some integer. The values of s seem to vary almost randomly, but as k increases, s never decreases. Refer to the tables attached in Appendix B for sample values.

The reason that these results are intriguing stem from the data for the case where l does not divide m. In these cases, no t-spaced periodicity is apparent. Furthermore, there does not appear to be a nice closed form expression for the continued fractions of τ, let alone its powers. It would be nice to have a proof of this, but I have yet to find one.

To summarize, we have thus far been able to determine closed form expressions for the continued fraction expansions of the following quadratic surds:

• type τ_{1}, numbers of the form: [\overline{a_{0}}]

• type τ_{2}, numbers of the form: [a_{0}, \overline{1, (a_{0} − 1)}]

• type τ_{3}, numbers of the form: [\overline{a_{0}, d}], where d|a_{0}.

∀a_{0} ∈ ℕ.

We have also been able to find closed form expressions for τ_{1}^{k} and τ_{2}^{k} ∀k ∈ ℕ. These are again of the form tau_{1} or tau_{2}. i.e. the shape of the integral powers of these τ’s are in some sense bounded.

On Repeating Blocks of Length Greater Than 2

So we have derived closed form expressions for τ^{k}’s associated with some continued fractions that have repeating blocks of lenght at most 2. But what about continued fractions that have larger repeating blocks? We noted earlier that continued fractions of repeating block one and two are generally well understood, and so in some sense they are trivial. The work we have done is not useless, since it does afford some structure to this group, but in order to be really useful,we need to extended the results to less trivial groups.

6.1 Repeating Blocks of Length 3

We first try to extend our technique to quadratic surds that have continued fraction expansions with a repeating block of length 3. The first step is to see which numbers of this form can be generated by second-order difference equations. After this, we will see if we can apply techniques similar to the last section to explicitly determine closed form expressions for the continued fraction of these numbers, and also their powers.

Suppose we have a continued fraction of the form τ = [\overline{a_{0}, a_{1}, a_{2}}]. Then τ = a_{0} + _{\frac{1}{a_{1}+_{\frac{1}{a_{2}+ \frac{1}{τ}}}}} . Simple algebraic manipulations (a series of subtractions

followed by inversions)yield:

(1 + a_{1}a_{2})τ^{2} = (a_{0} − a_{1} + a_{2} + a_{0}a_{1}a_{2})τ + (a_{0}a_{1} + 1)

⇒ τ^{2} = \frac{a_{0} − a_{1} + a_{2} + a_{0}a_{1}a_{2}}{1 + a_{1}a_{2}} + \frac{a_{0}a_{1} + 1}{1 + a_{1}a_{2}}  (6.1)

We now compare this to the general difference equation found in 4.1. Letting τ = lim_{n→∞} \frac{G_{n}}{G_{n−1}} and τ^{2} = lim_{n→∞} \frac{G_{n}}{G_{n−2}} , as usual, then we get:

τ^{2} = mτ + l  (6.2)

Equating 6.1 and 6.2, we see that τ can be expressed as a difference equation in the required form if and only if:

(1 + a_{1}a_{2}) | (a_{0}a_{1} + 1) and
(1 + a_{1}a_{2}) | (a_{0} − a_{1} + a_{2} + a_{0}a_{1}a_{2})  (6.3)

Instead of solving the above conditions for all solutions, we wrote a short program in mathematica that printed out all continued fraction conforming to 4.1 for all values of l ≤ 200 and m ≤ 800, that have repeating blocks of length 3. There are two forms that can satisfy this condition:

τ = [\overline{a_{0}, a_{1}, a_{2}}]  (6.4)
τ = [a_{0}, \overline{a_{1}, a_{2}, a_{3}}]  (6.5)

Now, armed with the experimental data, the next step was to use the observed forms to derive more general statements. That is, the first goal was to work backwards from the experimental data to outline conditions on the coefficients of the general difference equation from 4.1 that would generate quadratic surds of the discovered forms.

For τ’s of the form in 6.4, the experimental results suggested that in all cases, a_{1} = a_{2}. Upon closer examination of the data, it was discovered that the τ′s could be further subdivided into different classes, based on certain conditions on m and l. Although the analysis was not necessarliy exhaustive, the following three cases were outlined:

Case 1:

a_{0} = m = 2l − 1
a_{1} = a_{2} = 1

Case 2:

a_{0} = l(l − 1) + 1
a_{1} = a_{2} = l − 1

Case 3:

a_{1} = a_{2} = c
a_{0} ≡ c (mod (1 + c^{2})

Proofs: First notice that the first two cases are contained within the third. Therefore, we need only prove the third case. To do this, all we must do is verify the conditions outlined in 6.3. Let a_{1} = c = a_{2} , a_{0} = c ∗ (1 + c^{2}) + c , where , c ∈ ℤ. Then:

a_{0}a_{1} + 1 = c(c(1 + c^{2}) + c) + 1 = c^{4} + 2c^{2} + 1 = (c^{2} + 1)^{2} = (1 + a_{1}a_{2})^{2}

and,

a_{0} − a_{1} + a_{2} + a_{0}a_{1}a_{2} = c(1 + c^{2}) + c − c + c + c^{2}(c(1 + c^{2}) + c)
= (1 + c^{2})(c(1 + c^{2}) + c) = (1 + a_{1}a_{2}) ∗ a_{0}.

So we see both conditions are clearly satisfied.

Q.E.D.

These cases provided us with conditions on m and l. We were then able to generate sequences of k-neighbour ratios from difference equations whose coefficients satisfy these conditions. Printouts similar to those in Appendix A (for the Fibonacci case) were generated for the easier cases 1 and 2. From the data, we were unable to conclude any kind of t-spaced periodicity. It was therefore evident that for repeating blocks of length three, the treatment could not be the same as in our previous cases.

Nevertheless, we proceeded to analyze what happens to the powers of several of the tau’s generated by the limits of the neighbours of the derived difference equations. It was still a distinct possibility that the powers of these tau’s could be derived in a predictable way. This turned out not to be the case. Typically, the periods of the continued fractions of the powers of these τ’s changed wildly. Attached in Appendix B are the tables showing the length of the repeating block of τ^{k} for various values of k. The tables were divided based on the parity of k. This was necessary since the shapes of the continued fraction are dependent on k. For odd values of k, the continued fraction has the form:

τ^{k} = [\overline{a_{0}, a_{1}, ..., a_{n}}] For even values, the continued fraction has the form:

τ^{k} = [a_{0}, \overline{a_{1}, ..., a_{n}}]

From the results, the wild growth of the powers of τ is clearly evident. Mathematica could only handle small values of l and even smaller values of k. Although it would have been interesting to perform some analysis on the distribution of the lengths of the repeating block, we were not able to generate enough data. For example, with k relatively small (< 10), the lengths of the repeating block of some of the continued fractions were greater than 10^{6}. At the same time, however, some of the larger powers of some τ’s were handled rather easily. Therefore, although it appears that the repeating block length grows on average as k increases, this is not always true for a given m, l and k.

The τ′s of the form 6.5 led to some results that seemed a little more inspiring. It was determined that all τ’s that conform to the difference equations as in 4.1 satisfy the condition: a_{1} = a_{2}. (Note: both forms that conform to our general difference equation require two of the three partial quotients in the repeating block to be equal. Therefore, this method is severely restricted to a small class of ordered triplets that either have the first two elements, or the last two elements equal.)

As in the case of the first forms, the ratio of numbers in the sequence of continued fraction generated by the difference equations do not, exhibit any t-spaced periodicity. Here too we genrated data or the lengths of the repeating blocks of the powers of τ Unlike the previous case„ it was discovered that there was one case in which the continued fraction expansion of the square of τ was predictable from the continued fraction expansion of τ.

Suppose in 4.1, m = 1 and l is a square. Then, we deduce the following from the experimental data:

• a_{1} = 1 = a_{2}

• a_{3} = 2a_{0} − 1

Therefore

τ = [a_{0}, \overline{1, 1, 2a_{0} − 1}]

⇒ τ = a_{0} + \frac{1}{1 + _{\frac{1}{1+ \frac{1}{2a_{0}−1+τ−a_{0}}}}}

Simplifying yields:

τ = a_{0} + \frac{a_{0} + τ}{2a_{0} + 2τ − 1}

⇒ 2a_{0}τ + 2τ^{2} − τ = 2a_{0}^{2} + 2a_{0}τ − a_{0} + a_{0} + τ
⇒ τ^{2} = a_{0}^{2} + τ  (6.6)

Which confirms our observations for τ^{2}. This result is rather obvious upon a little reflection. Since m = 1, we know immediately that the coefficient of τ in the limiting procedure is one. Therefore, the fact that τ^{2} = l + τ is obvious. Such results seem to offer little in the way of insight, since they do not allow one to know anything about the higher powers of τ.

In order to demonstrate just how unpredictable the continued fraction expansions of higher orders of τ (k ≥ 3) really are, I have included a table with values for relatively small l and k ≤ 10 in Appendix C. It should be noted that unlike the previous case, the shape of the continued fractions of this form was the same for all k, i.e.:

τ^{k} = [a_{0}, \overline{a_{1}, …, a_{n}}]

for some integers a_{0}, a_{1}, …, a_{n}.

Again, although the repeating block lengths did grow in general with l and k, they do not do so with any predictability. For example, when l = 10^{2}, the repeating block lengths for k = 6, 7, 8 are 2154, 270,and 46670 respectively. For the next value of l in this family, i.e l = 11^{2}, the repeating block lengths for the same values of k are 60, 1482547, and 453176 respectively. Here too, the wide range of values of the lengths og the repeating blocks made distribution analysis unfeasible.

We can therefore conclude that the techniques that were useful in developing the underlying structure of some simple continued fractions of repeating block length one or two could not be extended to include repeating blocks of greater lengths. More precisely, the methods discussed in this paper seem to be applicable only to a small family of difference equations. While this result is somewhat disappointing, it is nonetheless instructive.

For Those Who Come After

When we began our research, we had hoped to capture a certain structure of continued fractions through an analysis in simple difference equations. Our results were very good at first, but soon it became apparent that the techniques employed could not satisfy more general cases than those already well-understood. In this respect, the project was somewhat of a disappointment.

However, the research did provide some insights that could be extended into future projects. For example, it is intriguing that under certain conditions, the length of the repeating block, and even its shape, are in a certain sense bounded. However, when not restricted to these cases, the length of the repeating block changes wildly. One nice project might be to analyze why these bounds exist in the most general case, and why there is such violation of bounds in others.

Another interesting project would be to analyze the conditions under which the sequence of continued fractions generated by k-nbr ratios of elements of a difference equation exhibit t-spaced periodicity. A good starting point may be to examine how the ’s’ from section 5.3 changes with k and τ.

Yet a third experiment that can come from this research is to see if the periodic continued fractions that we can generate with our techniques conform, in the limit, to Kuzmin’s theorem. This may seem unnatural at first. Kuzmin’s theorem predicts the probability of finding a certain integer in an infinite continued fraction expansion. The continued fractions that we have been generating are all periodic, and therefore contain only a finite number of integers. So Kuzmin’s theorem cannot apply. However,we may apply the theorem to numbers τ which have arbitrarily large repeating blocks. (For example, looking at our results in table C, we determined a continued fraction that has repeating block of 1758078 digits.)

Appendix A

Tables: Continued Fraction Expansions of Ratios of Fibonacci k-Neighbours

In this section, we post the tables of \frac{F_{n}}{F_{n−k}} for k = 3, 4, 5, 6 and for n= 20, 21, 22 ,…, 40.

The results for each k-value are posted on separate pages, in order of increasing k.

39 40 41 42

Appendix B

Tables: Length of the Repeating Blocks of the Powers of τ, where τ has the form: [\overline{a_{0}, a_{1}, …, a_{n}}]

In this section, we post the tables that find the lengths of the repeating blocks of some number generated by the second-order difference equation where m = 2l−1

The results for each k-value are posted on separate pages, in order of increasing k and increasing l. The first page reports findings for k odd. The next page for k even.

44 45

Appendix C

Tables: Length of the Repeating Blocks of the Powers of τ, where τ has the form: [a_{0}, \overline{a_{1}, …, a_{n}}]

In this section, we post the tables that find the lengths of the repeating blocks of some number generated by the second-order difference equation where m = 1and l = i^{2}, where i ∈ ℤ.

47 48 49 50 51

Bibliography

[BH] M. Bicknell, V. Hoggatt A Primer for the Fibonacci Numbers,The Fibonacci Association, San Jose, California 1973.

[Class Notes] Notes For Princeton Junior Seminar, Fall 2002 Diophantine Analysis and Roth’s Theorem R. Takloo-Bighash, S.J. Miller, H. Helfgott, F. Spinu , Princeton University 2002.

[DR] M. Drmota, “Fibonacci Numbers and Continued Fraction Expansions”, in G.E. Bergum et al.(eds.), Applications of Fibonacci Numbers Vol. 5. Second edition. Kluwer Academic Publishers. Netherlands 1993.

[BG] Bill Gosper, Continued Fraction Arithmetic (Unfinished), Retrieved Monday March 17, 2003. from: www.tweedledum.com/rwg/cfup.htm.

[mathworld.com] Quadratic Surd Retrieved Monday May 5, 2003. from www.mathworld.com.

[OR] J.J. O’Connor and E.F. Robertson, Leonardo Pisano Fibonacci, Retrieved Thursday January 16, 2003.from: www-gap.dcs.st-and.ac.uk/ history/Mathematicians/Fibonacci.html.

[AvP1] A.J. van der Poorten, An Introduction to Continued Fractions Retrieved Saturday April 5, 2003. from wwwcentre.mpce.mq.edu.au/alfpapers/a075.pdf.

[AvP2] A.J. van der Poorten, Fractional Parts of the Period of the Continued Fraction Expansion of Quadratic Integers Retrieved Saturday April 5, 2003. from www-centre.mpce.mq.edu.au/alfpapers/a090.pdf.