# Closed Form Continued Fraction Expansions of Special Quadratic Irrationals

Authors: Daniel Fishman; Steven J. Miller
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

We derive closed form expressions for the continued fractions of powers of certain quadratic surds. Specifically, consider the recurrence relationGn+1=mGn+ℓGn-1 with G0=0, G1=1, m a positive integer, and ℓ=±1 (note that m=ℓ=1 gives the Fibonacci numbers). Let φm,ℓ=limn→∞Gn/Gn-1. We find simple closed form continued fraction expansions for φm,ℓk for any integer k by exploiting elementary properties of the recurrence relation and continued fractions.


---

## Body

## 1. Introduction

In [1], van der Poorten wrote that the elementary nature and simplicity of the theory of continued fractions is mostly well disguised in the literature. This makes one reluctant to quote sources when making a remark on the subject and seems to necessitate redeveloping the theory ab initio. As our work is an outgrowth of [1], we happily refer the reader to that paper for some basic background information on continued fractions, and to the books [2, 3] for proofs. Briefly, every real number α has a continued fraction expansion
(1)α=a0+1a1+(1/(a2+(1/⋱))),
where each ai is an integer (and a positive integer unless i=0). The ai’s are called the partial quotients. For brevity we often write
(2)α=[a0,a1,a2,…].
If we truncate the expansion at an, we obtain the nth partial quotient
(3)pnqn=[a0,a1,a2,…,an].
The pn’s and qn’s satisfy the very important relation
(4)pnqn-1-pn-1qn=(-1)n-1.
Continued fractions encode much useful information about the algebraic structure of a number and frequently arise in approximation theory and dynamical systems. Clearly, α is rational if and only if its continued fraction is finite, and a beautiful theorem of Lagrange states that α is a quadratic irrational if and only if the continued fraction expansion is periodic.In this paper, we explore the continued fraction expansions of powers of quadratic surds. Recall that a quadratic surd is an irrational number of the formP±D/Q, where P,Q∈ℤ and D is a nonsquare integer. By Lagrange’s theorem we know these numbers and their powers have periodic continued fractions, which suggests many questions, such as what is the length of the period as well as what are the entries. Some special cases were done by van der Poorten in [1]. He studied solutions to Pell’s equation X2-DY2=±1, (D a nonsquare integer). Using the solution, he derived expansions for the continued fraction of D and (1+D)/2 (with D≡1mod4) and then for the expansions of some simple functions of these numbers as well as numbers related to Diophantine equations similar to Pell’s equation.Another technique that shows promise in manipulating continued fractions comes from an unfinished paper of Gosper [4]. He 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. His 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. Unfortunately, these algorithms, while useful for many applications, do not reveal the nature of the underlying structure in a closed form in an accessible manner.The purpose of this paper is to continue these investigations for additional families. We derive closed form expressions for the continued fractions of powers of certain quadratic surds.As the Fibonacci case is perhaps the most interesting, and some generalizations can be reduced to this case, we state the results there first. Letfk denote the kth Fibonacci number and Fn denote the nth Fibonacci number. The reason for using both upper and lower case letters for the Fibonacci numbers is to make the algebra in Section 2 visually easier to read by using upper case for the Fibonacci numbers whose subscript is variable. Set φ=limn→∞Fn/Fn-1, which is the golden mean; note φk=limn→∞Fn/Fn-k.Theorem 1.
One has the following:(5)FnFn-k={[fk+1+fk-1,Fn-kFn-2k]ifkiseven[fk+1+fk-1-1,1,Fn-kFn-2k-1]ifkisodd,
which yields
(6)φk={[fk+1+fk-1¯]ifkisodd[fk+1+fk-1-1,1,fk+1+fk-1-2-]ifkiseven.The techniques used to prove the above theorem can be extended to certain recurrence relations. Letgk=Gk for the same reason as before.Theorem 2.
Consider the recurrence relationGn+1=mGn+ℓGn-1 with G0=0, G1=1, m a positive integer, and ℓ=±1, again letting gk=Gk. Let
(7)φm,ℓ=limn→∞GnGn-1=m±m2+4ℓ2.
Then, for any positive integer k, if ℓ=1 one has
(8)φm,1k={[gk+1+gk-1¯]ifkisodd[gk+1+gk-1-1,1,gk+1+gk-1-2¯]ifkiseven,
while if ℓ=-1 one has
(9)φm,-1k=[gk+1-gk-1-1,1,(gk-1-gk-1-2)¯].The numerical data that led us to these results, as well as some additional experimental observations which, as of now, we have not been able to isolate into general theorems, are available at [5].On a personal note, this paper is an outgrowth of two undergraduate research classes taken by the first named author under the instruction of the second named author (and others) at Princeton University in 2002 and 2003. One of the topics covered was continued fractions, where many of Alf van der Poorten’s papers [1, 6–15] were read and enjoyed. These types of questions are ideally suited to introduce students to research. The results here, while later discovered to have been proved through other techniques (see e.g., [16]) were originally found through numerical exploration, which suggested the proof strategy.The second named author had the fortune of being at Brown University with Alf a few years later and remembers fondly numerous conversations on continued fractions and other topics in general, and the expansions in this paper in particular. Alf’s constant enthusiasm, knowledge of the field, and helpful comments greatly improved the exposition of continued fractions in [3], a textbook developed from the Princeton course.


## 2. Continued Fractions of Powers of the Golden Mean

As we will see later that the proof of Theorem2 reduces to the special case of the Fibonacci numbers, we study this case first. For notational convenience, we write Fn for the nth Fibonacci number when n varies and write fk for the kth Fibonacci number when k is a fixed input. This notation helps us visually parse the equations that follow.The following lemma collects some well-known properties of the Fibonacci numbers which will be useful below. The proofs are standard (see e.g., [17], especially Chapter 5).Lemma 3.
The Fibonacci numbers satisfy the following properties.(1)
Fn=Fn-1+Fn-2, F0=0, F1=1.(2)
φ=limn→∞(Fn/Fn-1)=(1+5)/2.(3)
Binet’s Formula:(10)Fn=15[(1+52)n-(1+52)n].(4)
Fn-2Fn-(Fn-1)2=(-1)n-1.(5)
Fn=fk+1Fn-k+fkFn-k-1.The relations discussed below were initially found by numerically exploring the finite continued fraction expansions ofFn/Fn-k. Note that for the golden mean φ=limn→∞Fn/Fn-1, we have
(11)φ=1+52=[1,1,1,1,1,…],limn→∞FnFn-k=limn→∞FnFn-1Fn-1Fn-2⋯Fn-(k-1)Fn-k=φk.Fork=2, it is trivial to find the continued fraction of φ2 since Fn=Fn-1+Fn-2 implies
(12)FnFn-2=1+Fn-1Fn-2.
Taking the limit as n→∞, we find
(13)φ2=limn→∞FnFn-2=1+φ=[2,1,1,1,1,…].Withk=3, however, the result is not as obvious. From Lemma 3 (5) we note that Fn=f3Fn-2+f2Fn-3=2Fn-2+Fn-3, which implies
(14)FnFn-3=1+2Fn-2Fn-3.
Unfortunately, in general there is no simple expression for the continued fraction of 2α given the expansion of α. Numerical computations of the continued fraction expansions of Fn/Fn-3 were found to have the form [4,4,…,ρ], where ρ is 3 if n≡1mod3, 5 if n≡2mod3, and 4 if n≡0mod3. This is easily proved, as after some algebra we find that
(15)FnFn-3=4+1Fn-3/Fn-6,
and the claim now follows from knowing the first few ratios. Further, we get the continued fraction expansion for φ3 simply by taking limits.Theorem1 states that this algebra can be generalized to any k, as we now show.Proof of Theorem1.
We have(16)FnFn-k=fk+1Fn-k+fkFn-k-1Fn-k=fk+1+fkFn-k-1Fn-k=fk+1+fk-1Fn-k-1+fk-2Fn-k-1Fn-k=fk+1+((fk-1Fn-k-1+fk-1Fn-k-2)+fk-2Fn-k-1-fk-1Fn-k-2)×(Fn-k)-1=fk+1+fk-1Fn-kFn-k+fk-2Fn-k-1-fk-1Fn-k-2Fn-k=(fk+1+fk-1)+fk-2Fn-k-1-fk-1Fn-k-2Fn-k.
As Fn-k-1=fkFn-k-k+fk-1Fn-k-k-1 and Fn-k-2=fk-1Fn-k-k-1+fk-2Fn-k-k-2, (16) becomes
(17)FnFn-k=(fk+1+fk-1)+(fk-2(fkFn-2k+fk-1Fn-2k-1)-fk-1(fk-1Fn-2k+fk-2Fn-2k-1))×(Fn-k)-1=(fk+1+fk-1)+fk-2(fkFn-2k)-fk-1(fk-1Fn-2k)Fn-k=(fk+1+fk-1)+Fn-2k[fk-2fk-(fk-1)2]Fn-k.
From Lemma3 (4) we know that fk-2fk-(fk-1)2=(-1)k-1. Using this and (17), (16) becomes
(18)FnFn-k=(fk+1+fk-1)+Fn-2k(-1)k-1Fn-k=(fk+1+fk-1)+(-1)k-1Fn-k/Fn-2k.
Ifk is odd then (-1)k-1=1 and so (18) becomes
(19)FnFn-k=(fk+1+fk-1)+1Fn-k/Fn-2k,
while if k is even then (-1)k-1=-1 and so (18) becomes
(20)FnFn-k=(fk+1+fk-1)+-1Fn-k/Fn-2k.
If k is even we must manipulate further, and (20) becomes
(21)FnFn-k=(fk+1+fk-1-1)+1-1Fn-k/Fn-2k.
Now,
(22)1-1Fn-k/Fn-2k=Fn-k-Fn-2kFn-k=1Fn-k/(Fn-k-Fn-2k)=11+(Fn-2k/(Fn-k-Fn-2k))=11+(1/((Fn-k-Fn-2k)/Fn-2k))=11+(1/((Fn-k/Fn-2k)-1)).
Taking the limit as n→∞ yields
(23)φk=fk+1+fk-1-1+11+(1/(φk-1)),
from which the continued fraction of φk easily follows.


## 3. The General Difference Equation

We now consider the more general difference equation(24)Gn=mGn-1+ℓGn-2
with the initial conditions G0=0, G1=1 (we need to choose initial conditions to explicitly write down a generalized Binet’s formula). The results from Lemma 3 immediately generalize; we omit the proofs (which are available in [5]) which are straightforward algebra and just collect the results below. As before, we use both Gn and gk for terms of the sequence to make the arguments below easier to visually parse.Lemma 4.
The authors’ sequence{Gn} satisfies the following properties.(1)
Gn=mGn-1+ℓGn-2 with G0=0, G1=1.(2)
φm,ℓ=limn→∞(Gn/Gn-1)=(m±m2+4ℓ)/2.(3)
Generalized Binet’s Formula:(25)Gn=1m2+4ℓ[(m+m2+4ℓ2)n-(m-m2+4ℓ2)n].(4)
Gn-2Gn-(Gn-1)2=(-1)n-1·ℓk-2.(5)
Gn=gk+1Gn-k+ℓgkGn-k-1.We want to find closed form expressions for the continued fractions of theφm,ℓk for integral k. As the continued fraction of α is trivially related to that of 1/α, it suffices to study k>0.We argue, as in Section2, from Lemma 4 (5) we have Gn=gk+1Gn-k+ℓgkGn-k-1, and thus
(26)GnGn-k=gk+1Gn-k+ℓgkGn-k-1Gn-k=gk+1+ℓgkGn-k-1Gn-k=gk+1+ℓmgk-1Gn-k-1+ℓgk-2Gn-k-1Gn-k=gk+1+ℓ((mgk-1Gn-k-1+ℓgk-1Gn-k-2)+ℓgk-2Gn-k-1-ℓgk-1Gn-k-2)×(Gn-k)-1=gk+1+ℓgk-1Gn-kGn-k+ℓℓgk-2Gn-k-1-ℓgk-1Gn-k-2Gn-k=(gk+1+ℓgk-1)+ℓ2gk-2Gn-k-1-gk-1Gn-k-2Gn-k.From Lemma4 (5), we have Gn-k-1=gkGn-k-k+ℓgk-1Gn-k-k-1. Also Gn-k-2=gk-1Gn-k-k-1+ℓgk-2Gn-k-k-2. Thus, (26) reduces to
(27)GnGn-k=(gk+1+ℓgk-1)+ℓ2(gk-2(gkGn-2k+ℓgk-1Gn-2k-1)-gk-1(gk-1Gn-2k+ℓgk-2Gn-2k-1))×(Gn-k)-1=(gk+1+ℓgk-1)+ℓ2gk-2gkGn-2k-gk-1gk-1Gn-2kGn-k=(gk+1+ℓgk-1)+ℓ2Gn-2k(gk-2gk-(gk-1)2)Gn-k.
From Lemma 4 (4) we know that
(28)gk-2gk-(gk-1)2=(-1)k-1ℓk-2,
and thus
(29)GnGn-k=(gk+1+ℓgk-1)+Gn-2kℓk(-1)k-1Gn-k.We now prove our main result.Proof of Theorem2.
Consider that we have the following cases.
Case1(ℓ=1).  In this case, the difference equation takes the form Gn=mGn-1+Gn-2. The functional form of (29) is identical to that of (18); the only difference is that we have g’s and G’s instead of f’s and F’s. We can thus quote our results from that case and obtain the desired result.
Case2(ℓ=-1).  When ℓ=-1 the difference equation is of the form Gn=mGn-1-Gn-2; we choose the initial conditions so that no term is ever negative. Taking ℓ=-1 in (29) gives
(30)GnGn-k=(gk+1+gk-1)+(-1)k-1(-1)kGn-2kGn-k=(gk+1+gk-1)-Gn-2kGn-k.
As this is of the same form as what we had in (20), we can argue as in Section 2. We have thus shown that all quadratic surds of the form φm,-1=(m+m2-4)/2, and their powers, have continued fraction expansions of the form
(31)φm,-1k=(gk+1-gk-1-1)+11+(1/(φm,-1k-1)).
This clearly determines a continued fraction with repeating block of length 2 of the following  form:
(32)φm,-1k=[gk+1-gk-1-1,1,(gk-1-gk-1-2)¯].
This is a completing of the proof.



---

*Source: 414623-2013-01-17.xml*