One of the most important ideas in dealing with Continued Fractions is the Continued Fraction Approximation Algorithm. This is an algorithm that can be used to convert a real number into a series of integers which make up the continued fraction.

The algorithm itself is made up of two equations which I will label p

_{n}and q

_{n}. Later, I will show that any finite continued fraction which represents an approximation of a real number is equal to a ratio of these two equations.

All of the ideas presented in today's blog are based on Harold M. Stark's Introduction to Number Theory.

Lemma 1: If [a

_{0}, a

_{1}, ... a

_{n}, α] is a continued fraction where all values a

_{i}are integers and α is any real number, then there exists series p

_{n}and q

_{n}where:

[a

_{0}, a

_{1}, ... a

_{n}, α ] = (α * p

_{n}+ p

_{n-1})/(α * q

_{n}+ q

_{n-1})

(1) Let [a

_{0},a

_{1}, ...a

_{n}, α] be a continued fraction such that:

[a

_{0},a

_{1},...a

_{n}, α ] = a

_{0}+ 1/[a

_{1}+ 1/(a

_{2}+ ... + 1/α)]

(2) Let p

_{n}be a sequence based on a

_{0}... a

_{n}such that:

p

_{0}= a

_{0}

p

_{1}= a

_{0}*a

_{1}+ 1

p

_{n+2}= (p

_{n+1})(a

_{n+2}) + p

_{n}

For example, p

_{2}= (p

_{1})(a

_{2}) + p

_{0}= (a

_{0}a

_{1}+ 1)(a

_{2}) + a

_{0}

(3) Let q

_{n}be a sequence based on a

_{0}... a

_{n}such that:

q

_{0}= 1

q

_{1}= a

_{1}

q

_{n+2}= (q

_{n+1})(a

_{n+2}) + q

_{n}

For example, q

_{2}= (q

_{1})(a

_{2}) + q

_{0}= (a

_{1})(a

_{2}) + 1

(4) So, consider the case where n = 1, then we have:

[a

_{0}, a

_{1}, α] = a

_{0}+ 1/[(a

_{1}+ 1/α)] = a

_{0}+ 1/[(a

_{1}α + 1)/α] = a

_{0}+ α/(a

_{1}α + 1) =

[a

_{0}(a

_{1}α + 1) + α]/(a

_{1}α + 1) = [α(a

_{0}a

_{1}+ 1) + a

_{0}]/(a

_{1}α + 1)

(5) Now, applying the definition given above for p

_{n}and q

_{n}gives us:

[a

_{0},a

_{1},α] = (α*p

_{1}+ p

_{0})/(α*q

_{1}+ q

_{0})

(6) So that, for n=1, we have:

[a

_{0}, a

_{1}, α] = (α*p

_{1}+ p

_{0})/(α*q

_{1}+ q

_{0})

(7) Let's assume that this is true up to some value n so that:

[a

_{0}, a

_{1}, ..., a

_{n}, α] = (α*p

_{n}+ p

_{n-1})/(α*q

_{n}+ q

_{n-1})

(8) Now, we know that: [a

_{0}, a

_{1}, ..., a

_{n}, a

_{n+1}, α] = [a

_{0}, a

_{1}, ..., a

_{n}, a

_{n+1}+ 1/α] by the definition of continued fractions.

(9) So by our assumption in #7:

[a

_{0}, a

_{1}, ..., a

_{n}, a

_{n+1}+ 1/α] = [(a

_{n+1}+ 1/α)*p

_{n}+ p

_{n-1}]/[(a

_{n+1}+ 1/α)*q

_{n}+ q

_{n-1}]=

(a

_{n+1}*p

_{n}+ p

_{n}/α + p

_{n-1})/(a

_{n+1}*q

_{n}+ q

_{n}/α + q

_{n-1})

(10) Now, multiplying the above by α/α gives us:

(a

_{n+1}*p

_{n}+ p

_{n}/α + p

_{n-1})/(a

_{n+1}*q

_{n}+ q

_{n}/α + q

_{n-1}) =

=(α*a

_{n+1}*p

_{n}+ p

_{n}+ α*p

_{n-1})/(α*a

_{n+1}*q

_{n}+ q

_{n}+ α*q

_{n-1}) =

=[α(a

_{n+1}p

_{n}+ p

_{n-1}) + p

_{n}]/[α(a

_{n+1}q

_{n}+ q

_{n-1}) + q

_{n}]

(11) And finally, applying the series p

_{n}and q

_{n}gives us:

[α(a

_{n+1}p

_{n}+ p

_{n-1}) + p

_{n}]/[α(a

_{n+1}q

_{n}+ q

_{n-1}) + q

_{n}] = (αp

_{n+1}+ p

_{n})/(αq

_{n+1}+ q

_{n)}

(12) Applying the principle of induction, we are done.

QED

Theorem 1: The Continued Fraction Approximation Algorithm

For any given finite continued fraction [ a

_{0}, a

_{1}, ... a

_{n}] where all a

_{i}are integers, using Lemma 1 to compute p

_{n}and q

_{n}we find that:

[ a

_{0}, a

_{1}, ... a

_{n}] = p

_{n}/ q

_{n}

(1) Let's define p

_{n}, q

_{n}using the series in Lemma 1.

(2) For case n=1, we have:

[a

_{0}, a

_{1}] = a

_{0}+ 1/a

_{1}= (a

_{0}*a

_{1}+ 1)/a

_{1 [By definition of Continued Fractions]= p1/q1 [By definition of pn and qn in Lemma 1]}

(3) Assume that this is true up to some value n so that [a

_{0}, a

_{1}, ... a

_{n}] = p

_{n}/q

_{n}

(4) Applying Lemma 1, gives us:

[a

_{0}, a

_{1}, ..., a

_{n}, a

_{n+1}] = [(a

_{n+1})p

_{n}+ p

_{n-1}]/(a

_{n+1})q

_{n}+ q

_{n-1}= p

_{n+1}/q

_{n+1}

(5) By the Principle of Induction, we are done.

QED

Now, consider this interesting lemma:

Lemma 2: p

_{n}*q

_{n-1}- p

_{n-1}*q

_{n}= (-1)

^{n-1}

(1) Let's start with the Case: n = 1

p

_{n}*q

_{n-1}- p

_{n-1}*q

_{n}= p

_{1}* q

_{0}- p

_{0}*q

_{1}

From Lemma 1 above,

p

_{0}= a

_{0}

p

_{1}= a

_{0}*a

_{1}+ 1

p

_{2}= p

_{1}a

_{2}+ p

_{0}= (a

_{0}a

_{1}+ 1)a

_{2}+ a

_{0}= a

_{0}a

_{1}a

_{2}+ a

_{2}+ a

_{0}

q

_{0}= 1

q

_{1}= a

_{1}

q

_{2}= q

_{1}a

_{2}+ q

_{0}= a

_{1}a

_{2}+ 1

p

_{1}q

_{0}= (a

_{0}*a

_{1}+ 1)*1 = a

_{0}*a

_{1}+1

p

_{0}*q

_{1}= a

_{0}*a

_{1}

So:

p

_{1}*q

_{0}- p

_{0}q

_{1}= a

_{0}*a

_{1}+ 1 - a

_{0}*a

_{1}= 1

(2) So let's assume that this is true up to n-1 so that we can assume:

p

_{n}-1*q

_{n-2}- p

_{n-2}*q

_{n-1}= (-1)

^{n-2}

(3) From Lemma 1, step #2 and step #3, we know that:

p

_{n}= p

_{n-1}*a

_{n}+ p

_{n-2}

and

q

_{n}= q

_{n-1}*a

_{n}+ q

_{n-2}

(4) So,

p

_{n}*q

_{n-1}- p

_{n-1}*q

_{n}= (p

_{n-1}*a

_{n}+ p

_{n-2})(q

_{n-1}) - (p

_{n-1})(q

_{n-1}a

_{n}+ q

_{n-2})

= p

_{n-1}*a

_{n}*q

_{n-1}+ p

_{n-2}q

_{n-1}- p

_{n-1}*a

_{n}*q

_{n-1}- p

_{n-1}q

_{n-2}=

= p

_{n-2}q

_{n-1}- p

_{n-1}q

_{n-2}=

= (-1)(p

_{n-1}q

_{n-2}- p

_{n-2}q

_{n-1}) =

= (-1)(-1)

^{n-2}[From step #2 above]

= (-1)

^{n-1}

(4) By the Principle of Induction we are done.

QED

Lemma 3: If α is a positive real number and α = [a

_{0}, a

_{1}... a

_{n-1}, α

_{n}], then a

_{0}≥ 0 and all other a

_{i}≥ 1, and α

_{n}≥ 1.

(1) a

_{0}= floor(α) which clearly ≥ 0.

(2) In case n = 1, α

_{1}= 1/(α - a

_{0}).

In this case, a

_{0}is less than α (since we are assuming that α

_{n}is a nonzero real number).

So, clearly α

_{1}must also be a positive number greater than 1 (since the difference between α and a

_{0}is less than 1)

(3) In case n=2, a

_{1}= floor(α

_{1}) is ≥ 1 by the reasoning in step #2. With α

_{1}≥ 1 and a

_{1}≥ 1, we know that α

_{2}= 1/(α

_{1}- a

_{1}) must also be a positive number ≥ 1.

(4) Let's assume that this is true up to n-1.

(5) At this point, we have a value α

_{n}that is a positive real number ≥ 1.

(6) So, a

_{n}= floor(α

_{n}) which means that a

_{n}≥ 1.

(7) Finally, α

_{n+1}= 1/(α

_{n}- a

_{n}) which means that it too will be a positive real number ≥ 1.

(8) By the principle of induction we are done.

QED

Corollary 3.1: If α is a negative real number, and α = [a

_{0}, a

_{1}... a

_{n-1}, α

_{n}], then a

_{0}≤ 0 and all other a

_{i}≤ -1, and α

_{n}≤ 1.

(1) The reasoning here is the same as Lemma 3 except that we use a ceiling function instead of a floor function where ceiling (-5.6) = -5. In this case, the a

_{i}is higher than the α

_{i}value and the subtraction is still a negative number.

(2) In this way, we can use the same reasoning as Lemma 3 and we get the result that the answer is the same as in Lemma 3 except that we multiply -1 to all the a

_{i}values and also the α

_{n}value.

QED

Lemma 4: For a positive real number, if n is greater than 0, then q

_{n+1}is greater than q

_{n}

(1) For case n=1:

q

_{1}= a

_{1}

q

_{2}= q

_{1}a

_{2}+ q

_{0}= a

_{1}*a

_{2}+ 1

Since a

_{1}, a

_{2}are both ≥ 1, we know that:

a

_{1}≤ a

_{1}*a

_{2}

And therefore:

a

_{1}is less than a

_{1}*a

_{2}+ 1

(2) Let's assume that this is true up to n so that q

_{n+1}is greater than q

_{n}

(3) So, q

_{n+2}= q

_{n+1}*a

_{n+2}+ q

_{n}

(4) We know that q

_{1}= a

_{1}which means that q

_{1}≥ 1. [From Lemma 3]

(5) So q

_{n}is greater than 1 (by our assumption in #2)

(6) We also know that a

_{n+2}is ≥ 1 which gives us:

q

_{n+1}≤ q

_{n+1}*a

_{n+2}

(7) And finally, applying #5

q

_{n+1}is less than q

_{n+1}*a

_{n+2}+ 1 ≤ q

_{n+1}*a

_{n+2}+ q

_{n}= q

_{n+2}

(8) By the Principle of Induction, we are done.

QED

Corollary 4.1 For a positive real number where n is greater than 0, q

_{n}≥ n.

(1) Let's start with n=1

q

_{1}= a

_{1}which is ≥ 1.

(2) Let's assume that this is true up to n+1 so that q

_{n+1}≥ n+1.

(3) q

_{n+2}= q

_{n+1}a

_{n}+ q

_{n}

(4) Now q

_{n+2}is greater than q

_{n+1}which means that:

q

_{n+2}≥ q

_{n+1}+ 1 ≥ n + 1 + 1 ≥ n + 2.

(5) By the Principle of Induction, we are done.

QED

Corollary 4.2: We can also see for all values of n ≥ 2, p

_{n}, p

_{n+1}is greater than p

_{n}.

(1) We see that this is true for n=2:

p

_{1}= a

_{0}a

_{1}+ 1.

p

_{2}= p

_{1}a

_{2}+ a

_{0}.

p

_{3}= p

_{2}a

_{3}+ p

_{1}

Since a

_{0}is ≥ 0 (see above), we see that p

_{1}is ≥ 1.

Now a

_{3}is ≥ 1 so p

_{2}* a

_{3}is at least equal to p

_{2}but since p

_{1}is ≥ 1, we know that p

_{3}must be greater.

(2) Now, we assume it is true for all values up to n.

(3) p

_{n+1}= p

_{n}a

_{n+1}+ p

_{n-1}

Since p

_{1}≥ 1, from (1), we know that p

_{3}is ≥ 1 and all values of n greater than 3 is greater than 1.

So, we know that p

_{n+1}is greater than p

_{n}by at least p

_{n-1}which is ≥ 1.

(4) We have now proven that p

_{n+1}is greater than p

_{n}for all values of n ≥ 2.

QED

Theorem 2: For a positive irrational number, we can use the approximation algorithm to generate an approximation of any degree of accuracy. In other words:

absolute(α - p

_{n}/q

_{n}) is less than 1/(q

_{n}q

_{n+1}) which is less than 1/(q

_{n})

^{2}which is ≤ 1/n

^{2}

(1) From Lemma 1, we know that:

α = (α

_{n+1}p

_{n}+ p

_{n-1})/(α

_{n+1}q

_{n}+ q

_{n-1})

(2) Subtracting both sides by p

_{n}/q

_{n}gives us:

α - p

_{n}/q

_{n}= (α

_{n+1}p

_{n}+ p

_{n-1})/(α

_{n+1}q

_{n}+ q

_{n-1}) - p

_{n}/q

_{n}=

[q

_{n}(α

_{n+1}p

_{n}+ p

_{n-1}) - p

_{n}(α

_{n+1}q

_{n}+ q

_{n-1})]/[q

_{n}(α

_{n+1}q

_{n}+ q

_{n-1})] =

= (q

_{n}α

_{n+1}p

_{n}- q

_{n}α

_{n+1}p

_{n}+ p

_{n-1}q

_{n}- p

_{n}q

_{n-1})/[q

_{n}(α

_{n+1}q

_{n}+q

_{n-1}) ] =

= (p

_{n-1}q

_{n}- p

_{n}q

_{n-1})/[q

_{n}(α

_{n+1}q

_{n}+ q

_{n-1})] =

= (-1)

^{n}/[q

_{n}(α

_{n+1}q

_{n}+ q

_{n-1})]

(3) We know that for positive irrational numbers, a

_{n}is less than α

_{n}which means that:

1/[q

_{n}(a

_{n+1}q

_{n}+ q

_{n-1})] is greater than 1/[q

_{n}(α

_{n+1}q

_{n}+ q

_{n-1})]

Likewise,

-1/[q

_{n}(a

_{n+1}q

_{n}+ q

_{n-1})] is less than 1/[q

_{n}(α

_{n+1}q

_{n}+ q

_{n-1})]

(4) Now, we need to consider two cases to complete the proof:

Case I: n is even

In this case:

α - p

_{n}/q

_{n}is less than 1/[q

_{n}(a

_{n+1}q

_{n}+ q

_{n-1})] = 1/(q

_{n}q

_{n+1})

We also know that α - p

_{n}is greater than 0 which means that it is also greater than -1/(q

_{n})

^{2}

Since q

_{n+1}is greater than q

_{n}, we also know that:

α - p

_{n}/q

_{n}is less than 1/(q

_{n}q

_{n}) = 1/(q

_{n)}

^{2}

Putting all this together gives us,

absolute(α - p

_{n}/ q

_{n}) is less than 1/(q

_{n})

^{2}

Case II: n is odd

In this case:

α - p

_{n}/q

_{n}is greater than -1/[q

_{n}(a

_{n+1}q

_{n}+ q

_{n-1})] = -1/(q

_{n}q

_{n+1})

We also know that α - p

_{n}is less than 0 which means that it is also less than 1/(q

_{n})

^{2}

Since q

_{n+1}is greater than q

_{n}, we also know that:

α - p

_{n}/q

_{n}is greater than -1/(q

_{n}q

_{n}) = -1/(q

_{n)}

^{2}

Putting all this together gives us,

absolute(α - p

_{n}/ q

_{n}) is less than 1/(q

_{n})

^{2}

(5) Now, since q

_{1}≥ 1 and q

_{n+1}is greater than q

_{n}for n ≥ 1, we know that:

q

_{n}≥ n and:

1/(q

_{n})

^{2}is less than 1/n

^{2}

QED

Lemma 5: Let C

_{n}= p

_{n}/q

_{n}, then:

(a) C

_{n}- C

_{n-1}= [(-1)

^{n-1}]/(q

_{n}q

_{n-1})

(b) C

_{n}- C

_{n-2}= [a

_{n}(-1)

^{n}]/(q

_{n}q

_{n-2})

(1) p

_{n}q

_{n-1}- q

_{n}p

_{n-1}= (-1)

^{n-1}. [From Lemma 2 above]

(2) Dividing both sides by q

_{n}q

_{n-1}gives us (a).

(3) C

_{n}- C

_{n-2}= p

_{n}/q

_{n}- p

_{n-2}/q

_{n-2}= (p

_{n}q

_{n-2}- p

_{n-2}q

_{n})/(q

_{n}q

_{n-2})

(4) p

_{n}q

_{n-2}- p

_{n-2}q

_{n}= (a

_{n}p

_{n-1}+ p

_{n-2})q

_{n-2}- p

_{n-2}(a

_{n}q

_{n-1}+ q

_{n-2}) =

= a

_{n}(p

_{n-1}q

_{n-2}- p

_{n-2}q

_{n-1}) = a

_{k}(-1)

^{n-2}

(5) Combining #3 and #4 gives us (b).

QED

Corollary 5.1 C

_{1}is greater than C

_{3}is greater than C

_{5}... and C

_{0}is less than C

_{2}is less than C

_{4}...

(1) From Lemma 5(b), we know that C

_{n}is less than C

_{n-2}if n is odd and C

_{n}is greater than C

_{n-2}if n is even.

QED

Corollary 5.2 Consecutive C

_{n}lie above or below the exact value of the continued fraction.

(1) From Lemma 5, we know that they will alternate. For odd values of n, C

_{n}will be greater than C

_{n-1}and for even values of n, C

_{n}will be less than C

_{n-1}.

(2) By Theorem 2, we see that each C

_{n}is a value closer to the exact value of the continued fraction.

(3) Finally, from Theorem 2, step #2, we see that α - p

_{n}/q

_{n}is alternately above and below the main value. If n is even, then α is above and if it is odd, then α is below.

QED

Lemma 6: For any value n ≥ 1, gcd(p

_{n},q

_{n}) = 1.

(1) Assume that f divides both p

_{n}and q

_{n}

(2) By Lemma 2 above, p

_{n}q

_{n-1}- p

_{n-1}q

_{n}= (-1)

^{n-1}

(3) So f divides both implies that f divides (-1)

^{n-1}

(4) But the only way this is true is if f = 1.

(5) Which proves that the only common factor they can have is 1.

QED

## 5 comments:

In Lemma 2 (3):

Shouldn't you be factoring the qn+1 and pn+1?

Rob

Hi Rob,

Thanks very much for your question. I've rewritten Lemma 2 to make it clearer. I hope that this answers your question.

Cheers,

-Larry

In step (4) of

Theorem 1:[(an+1)pn+pn-1]/(an+1)qn+qn-1

should be:

[(an+1)pn + pn-1]/

[(an+1)qn+qn-1]In step (4) of

Theorem 2Should

We also know that α-pn is greater than 0be

We also know that α - pn/qnis greater than 0Rob

In step (4) of

Lemma 5an(pn-1qn-2-pn-2qn-1)=ak(-1)^n-2

Should be

an(pn-1qn-2-pn-2qn-1)=a

(-1)^n-2nPost a Comment