Closed Form Continued Fraction Expansions of Special Quadratic Irrationals

Dan Fishman^{1} Mathematics Department

Princeton University Princeton, NJ 08544

January 23, 2003

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

Abstract

We construct 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, where m ∈ ℕ and b_{n} = 1 for all n; note: m = 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}}; 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 2 1.1 An Introduction to Continued Fractions . . . . . . . . . . . . . . 2 1.2 Known Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 The simple Model . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Background on Fibonacci Numbers 5 2.1 Brief History on Fibonacci Numbers . . . . . . . . . . . . . . . . 5 2.2 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Experimental Results 7

4 The Continued Fraction Expansion of any Ratio of Fibonacci k-Neighbour Terms 9 4.1 A Proof in Full Generality for Fibonacci Ratios . . . . . . . . . . 10 4.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

5 the General Difference Equation 14 5.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2 More Closed Form Expressions . . . . . . . . . . . . . . . . . . . 18

6 For Those Who Come After 21

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

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} 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}, ...] c

Continued fractions turn out to be convenient representations of numbers since they provide the best approximation to a given number.

The one problem that we have encountered during the semester with continued fractions is that they are not easy to manipulate. Although integer shifts are handled easily, rational shifts, or even integer multiples are not easy to explicitly determine. For example, even doubling a continued fraction can lead to a result that is difficult to predict.

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 uglier as the number of terms in the continued fraction expansion increases.

Therefore, it would be useful to develop a good understanding of the fundamental structure of continued fractions . Although this is somewhat of a daunting task, my goal is to develop closed form expressions for some simple families, and then try to generalize the findings.

1.2 Known Results

Before we proceed, we will need a few basic results.

Lemma 1.2.1. 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.

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

We call \frac{p_{n}}{q_{n}} the nth convergent of α where:

p_{0} = a_{0}, p_{1} = a_{0}a_{1} + 1 , ... , p_{n} = a_{n}p_{n−1} + p_{n−2}
q_{0} = 1, q_{1} = a_{0} , ... , q_{n} = a_{n}q_{n−1} + q_{n−2}

see [Class Notes: Ch. 5, Convergence to a Continued Fraction ]

Clearly,\frac{p_{n}}{q_{n}} = a_{0} + _{\frac{1}{a_{1}+_{\frac{1}{^{...}+ \frac{1}{an}}}}}

We therefore see that any rational number is exactly determined by its last convergent, and every number is closely approximated by its n^{th} convergent as n gets very large.

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

Lemma 1.2.2.

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

1.3 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}. and since a_{n} = 1 for all n, we see that:

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

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 by now, 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}

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 5.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.2:

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 5.1.4)

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

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 approaches ∞, 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 with period k. 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 n, 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).

Could these results be generalized? The answer to this question turns out to be yes! The method is developed in the next chapter.

The Continued Fraction Expansion of any Ratio of Fibonacci k-Neighbour Terms

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 ecperimental 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. Since the parity even and odd values for k appeared to behave differently, 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.

4.1 A Proof in Full Generality for Fibonacci Ratios

Given a ratio of k-neighbour terms 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}}  (4.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 4.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−2k}}{F_{n−k}}}  (4.2)

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

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

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

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

Then we must manipulate further, so that Equation 4.4 becomes

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

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}}}

4.2 Analysis

The results that were just derived reflect exactly what we see in the experimental data. In the first place, we see that for all k (even and odd), the continued fraction expansion is periodic of degree k.

In the case of odd k,

\frac{F_{n}}{F_{n−k}} = [f_{k+1} + f_{k−1}, \frac{F_{n−k}}{F_{n−2k}} ]  (4.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. This confirms the observation that the Continued Fractions are periodic of period k.

In the case of even k,

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

which, again, exhibits the same periodicity of degree k. 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 ration.

(\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}} (4.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 4.5 if k is odd, or 4.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, 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, ..,]

5.1 Basic Properties

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

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

With the same initial conditions as before: G_{1} = G_{2} = 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 5.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}} = x

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

solving for x using the quadratic formula yields \frac{m±\sqrt{m^{2}+4l}}{2} The general difference equation has an equivalent Binet form: Proposition 5.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}  (5.2)
and let C_{1} = \frac{1}{\sqrt{m^{2} + 4l}} , C_{2} = −C_{1}  (5.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)]  (5.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 5.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. Now to see the equivalent of 2.2.4 Proposition 5.1.3. G_{n−2}G_{n} − (G_{n−1})^{2} = (−1)^{n−1} ∗ l^{k−2}

Proof: Again using the substitutions from 5.2 and 5.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  (5.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]  (5.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}  (5.7)

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

We must still verify the last property, however.

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

Again, we use the substitutions from 5.2 and 5.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} )  (5.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} )

And so 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 5.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 5.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}  (5.9)

as desired.

Again, 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.

5.2 More Closed Form Expressions

In this section, 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{1±\sqrt{m^{2}+4}}{2} where m ∈ ℕ

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

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

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}} Apply the technique from Chapter 4 to \frac{G_{n}}{G_{n−k}} gives the following: From Proposition 5.1.4: G_{n} = g_{k+1}G_{n−k} + g_{k}G_{n−k−1}

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

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

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

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

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

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

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

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

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

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

From proposition 5.1.3,

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

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

And so we see that this is precisely what we derived in 4.2!

So we have bow been able to determine explicitly the continued fraction expansion of all quadratic irrational numbers τ of the form: \frac{1±\sqrt{m^{2}+4}}{2} where m ∈ ℕ and for any positive, integral power of τ .

Again, as in the case of the Fibonacci sequence, we see that the periodicty of the continued fraction expansion is determined by the exponent k.

For Those Who Come After

The techniques developed in this paper have allowed us to determine closed form expressions for the continued fraction expansions of some special quadratic numbers. This result is helpful in the following ways:

First, we now have a nice set of closed form expressions which we can input into a database. For these special numbers, the usual algorithm to find the continued fraction expansion would not be necessary. However, since our method applies only to a relatively small class of numbers, it does not allow us to abandon the algorithm.

Second, we have been able to prove the structure of the continued fraction of a sizeable class of numbers. Although it was pretty clear at the outset that there was a nice structure to this class, we have successfully proven it, and can now use these results to possibly derive similar results for other classes.

There were a few reasons why we could not extend these results any further. In the first place, our method requires a periodic continued fraction expansion, and therefore cannot be extended to any algebraic irrational of degree higer than 2. It would be nice to have a general form that works for difference equations of the form, say J_{n} = aJ_{n−1} + bJ_{n−2} + cJ_{n−3} Applying the limiting techniques from the proof of 2.2.2, we see that if

τ = lim_{n→∞} \frac{J_{n}}{J_{n−1}}

then

τ = 1 + \frac{1}{τ} + \frac{1}{τ^{2}}

And so τ would be algebraic of degree 3. This would then preclude the existence of a periodic continued fraction expansion.

However, there are still several apporaches that can be taken for those who wish to pursue this project.

First, as mentioned earlier, the method generally requires the coefficient, l of the G_{n−2} term to be 1. However, a coefficient of −1 can also work, aslong as m, the the coefficient of the G_{n} − 1 term is greater than 1. Otherwise, the sequence degenerates to zero, and the continued fraction expansion as, n ⟶ ∞, becomes trivial. It would be interesting to find other possible values of l and m for which our method remains valid.

In the same light, it was also determined that our technique can fail when the coefficient of G_{n−1} is non-integral. One key to the technique is that the leading term a_{0} of the continued fraction expansion is f_{k+1} + fk − 1. Since we require this term to be integral, a new method must be found, that either assures that f_{k+1} + fk − 1 is integral, or how to decompose further to arrive at an integral term. This again is left open to the reader.

A third possibility is to consider difference equations for which the coefficent of G_{n−1} varies. This would certainly require new techniques.

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.

24 25 26 27

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.

[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.