# Proof for a theorem about relations beween convergents in continued fractions

Upon reading about some properties of numerators and denominators in a textbook called Continued Fractions (here, chapter 2.3), I was unable to understand the following transmutation of the expression (circled in red in the image link), and highlighted red here:

2.3 Relations between convergents In this section, we see some properties of the simple continued fractions in terms of the numerators and denominators appearing in the convergents.

Theorem 2.4. If $$p_{n}$$ and $$q_{n}$$ are defined by $$\begin{array}{l} p_{0}=a_{0}, p_{1}=a_{1} a_{0}+1, p_{n}=a_{n} p_{n-1}+p_{n-2} \text { for } 2 \leq n \\ q_{0}=1, q_{1}=a_{1}, q_{n}=a_{n} q_{n-1}+q_{n-2} \text { for } 2 \leq n \end{array}$$

then $$\left[a_{0}, a_{1}, \ldots, a_{n}\right]=\frac{p_{n}}{q_{n}}$$

Proof. The proof proceeds by induction. The base cases are seen to be true by the assumptions given for $$n=0, n=1$$. Let us assume the statement to be true for some $$m$$. Then

$$\left[a_{0}, a_{1}, \ldots a_{m-1}, a_{m}\right]=\frac{p_{m}}{q_{m}}=\frac{a_{m} p_{m-1}+p_{m-2}}{a_{m} q_{m-1}+q_{m-2}}$$

Hence, we get

$$\left[a_{0}, a_{1}, \ldots a_{m-1}, a_{m},\color{red}{a_{m+1}}\right]=\left[a_{0}, a_{1}, \ldots a_{m-1}, \color{red}{a_{m}+\frac{1}{a_{m+1}}}\right]$$

In addition to not seeing how the equality in the last line was achieved, I was also under the impression that convergents of continued fractions (the quotients in square bracket notation) must by definition always be integers. The marked transmutation makes the last quotient a fraction.

• continued fractions are pretty easy to calculate; if you get good at that the notation that now worries you will be transparent. To begin, it is just a way to do the extended Euclidean Algorithm. – Will Jagy Apr 3 at 1:24
• My personal interest is in the relationship between continued fractions and the Pell equation. As a supplemental text, that is on a math sophistication par with the pdf that you referenced, I recommend this pdf. You will have to be careful, however, because the formulas will be different, since the alternate notation of $[a_1, a_2, \cdots]$ rather than $[a_0, a_1, \cdots]$ is used. ...see next comment – user2661923 Apr 3 at 3:06
• For a much more advanced treatment, that I don't recommend that you tackle until after completing the pdf referenced in the previous comment, I recommend this 2nd pdf. Personally, I never went beyond chapter 1 in the 2nd pdf, because that chapter had everything I needed, with respect to the Pell equation. If you do get through these, and you have further interest, you will see many mathSE queries that involve continued fractions or the Pell Equation. In fact, many of the answers of Will Jagy, who you can search on, are on one or both of these topics. – user2661923 Apr 3 at 3:10
• It is best to put the relevant portions of your linked pdf and image in the body of question. I have voted to close as "needs details or clarity". – Paramanand Singh Apr 3 at 3:26

This is an interpretation question, rather than a request for a problem to be solved. Therefore, I personally see no problem answering it, even though the OP has shown no work. If I get downvoted, okay.

Because of the difficulty displaying long continued fractions, I am going to illustrate the OP's question, under the assumption that $$m = 3$$.

$$a_0 +\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3 + \cfrac{1}{a_4}}}}$$

can be equivalently interpeted as

$$a_0 +\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\{a_3 + \frac{1}{a_4}\}}}}$$

I was also under the impression that convergents of continued fractions (the quotients in square bracket notation) must by definition always be integers.

I am assuming that you intend the coefficients of continued fractions, which are normally expressed as integers, rather than the convergents of continued fractions, which normally have form $$\frac{p_n}{q_n}.$$

While it's true that the coefficients are normally computed to be integers, you specifically asked how a specific line in a proof can be algebraically justified. As indicated in my continued fraction examples above, the algebra is justified.

In my examples, what this means is that

$$[a_0, a_1, a_2, a_3, a_4]$$

is algebraically equivalent to

$$\left[a_0, a_1, a_2, \left(a_3 + \frac{1}{a_4}\right)\right].$$

• Indeed, I was confused about convergents and coefficients . Skipping over the gratitude 'noises' for superb answer - You've referenced a couple of pdf's that appear to be more detailed and thorough in explanations than what I had found. Would You happen to have a list of Your personal favorite reading resources posted somewhere? At a risk of going way off-topic - I'm interested in software engineering, thus, anything from calculus, abstract algebra, mathematical logic, graph theory, set theory, linear algebra, number theory, numerical methods, probability and statistics. – Whyitbenotworkin Apr 4 at 10:42
• @Whyitbenotworkin first see my answer to this question. My answer, which will be the one at the bottom, discusses generic book searching tips. Beyond that, books that I have used are [1] "Calculus, Volumes I and II" (2nd Edition, Tom Apostol, 1966) [2] "Elementary Number Theory" (Uspensky and Heaslet, 1939) and [3] "An Introduction To Complex Function Theory" (Bruce Palka, 1991). – user2661923 Apr 4 at 23:56

here's an example, including the Bezout equation at the end

$$\gcd( 479, 231 ) = ???$$

$$\frac{ 479 }{ 231 } = 2 + \frac{ 17 }{ 231 }$$ $$\frac{ 231 }{ 17 } = 13 + \frac{ 10 }{ 17 }$$ $$\frac{ 17 }{ 10 } = 1 + \frac{ 7 }{ 10 }$$ $$\frac{ 10 }{ 7 } = 1 + \frac{ 3 }{ 7 }$$ $$\frac{ 7 }{ 3 } = 2 + \frac{ 1 }{ 3 }$$ $$\frac{ 3 }{ 1 } = 3 + \frac{ 0 }{ 1 }$$ Simple continued fraction tableau:
$$\begin{array}{cccccccccccccc} & & 2 & & 13 & & 1 & & 1 & & 2 & & 3 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 27 }{ 13 } & & \frac{ 29 }{ 14 } & & \frac{ 56 }{ 27 } & & \frac{ 141 }{ 68 } & & \frac{ 479 }{ 231 } \end{array}$$  $$479 \cdot 68 - 231 \cdot 141 = 1$$

================================================

different, infinite but periodic continued fraction, here for $$\sqrt {13}$$

$$\sqrt { 13} = 3 + \frac{ \sqrt {13} - 3 }{ 1 }$$ $$\frac{ 1 }{ \sqrt {13} - 3 } = \frac{ \sqrt {13} + 3 }{4 } = 1 + \frac{ \sqrt {13} - 1 }{4 }$$ $$\frac{ 4 }{ \sqrt {13} - 1 } = \frac{ \sqrt {13} + 1 }{3 } = 1 + \frac{ \sqrt {13} - 2 }{3 }$$ $$\frac{ 3 }{ \sqrt {13} - 2 } = \frac{ \sqrt {13} + 2 }{3 } = 1 + \frac{ \sqrt {13} - 1 }{3 }$$ $$\frac{ 3 }{ \sqrt {13} - 1 } = \frac{ \sqrt {13} + 1 }{4 } = 1 + \frac{ \sqrt {13} - 3 }{4 }$$ $$\frac{ 4 }{ \sqrt {13} - 3 } = \frac{ \sqrt {13} + 3 }{1 } = 6 + \frac{ \sqrt {13} - 3 }{1 }$$

Simple continued fraction tableau:
$$\begin{array}{cccccccccccccccccccccccc} & & 3 & & 1 & & 1 & & 1 & & 1 & & 6 & & 1 & & 1 & & 1 & & 1 & & 6 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 3 }{ 1 } & & \frac{ 4 }{ 1 } & & \frac{ 7 }{ 2 } & & \frac{ 11 }{ 3 } & & \frac{ 18 }{ 5 } & & \frac{ 119 }{ 33 } & & \frac{ 137 }{ 38 } & & \frac{ 256 }{ 71 } & & \frac{ 393 }{ 109 } & & \frac{ 649 }{ 180 } \\ \\ & 1 & & -4 & & 3 & & -3 & & 4 & & -1 & & 4 & & -3 & & 3 & & -4 & & 1 \end{array}$$

$$\begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 13 \cdot 0^2 = 1 & \mbox{digit} & 3 \\ \frac{ 3 }{ 1 } & 3^2 - 13 \cdot 1^2 = -4 & \mbox{digit} & 1 \\ \frac{ 4 }{ 1 } & 4^2 - 13 \cdot 1^2 = 3 & \mbox{digit} & 1 \\ \frac{ 7 }{ 2 } & 7^2 - 13 \cdot 2^2 = -3 & \mbox{digit} & 1 \\ \frac{ 11 }{ 3 } & 11^2 - 13 \cdot 3^2 = 4 & \mbox{digit} & 1 \\ \frac{ 18 }{ 5 } & 18^2 - 13 \cdot 5^2 = -1 & \mbox{digit} & 6 \\ \frac{ 119 }{ 33 } & 119^2 - 13 \cdot 33^2 = 4 & \mbox{digit} & 1 \\ \frac{ 137 }{ 38 } & 137^2 - 13 \cdot 38^2 = -3 & \mbox{digit} & 1 \\ \frac{ 256 }{ 71 } & 256^2 - 13 \cdot 71^2 = 3 & \mbox{digit} & 1 \\ \frac{ 393 }{ 109 } & 393^2 - 13 \cdot 109^2 = -4 & \mbox{digit} & 1 \\ \frac{ 649 }{ 180 } & 649^2 - 13 \cdot 180^2 = 1 & \mbox{digit} & 6 \\ \end{array}$$

Something I programmed recently; this is the Gauss-Lagrange method of chains of reduced forms, here I use the left neighbors. The Pell equation deals with $$x^2 - n y^2,$$ the continued fraction being for $$\sqrt n.$$ With little extra effort we get the continued fraction for $$\frac{B + \sqrt D}{2A},$$ where $$D=B^2 -4AC.$$

I also have it print some 2 by 2 matrices in proper format for pari-gp; in each case below, the product pari calls rt * h * r is something specific related to the original Hessian matrix h

The "partial quotients" of the continued fraction are the absolute values of the "digits" I write at the right hand side of each line. The output below shows $$\frac{5 + \sqrt {597}}{22}$$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$$jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$$ ./indefCycleLeft 11 5 -13

0  form   11 5 -13   epsilon  1
1  form   -7 17 11   Epsilon  -2
2  form   17 11 -7   Epsilon  1
3  form   -1 23 17   Epsilon  -23     ambiguous
4  form   17 23 -1   Epsilon  1     ambiguous
5  form   -7 11 17   Epsilon  -2
6  form   11 17 -7   Epsilon  1
7  form   -13 5 11   Epsilon  -1 opposite
8  form   3 21 -13   Epsilon  7     ambiguous
9  form   -13 21 3   Epsilon  -1     ambiguous
10  form   11 5 -13

form   11 x^2  + 5 x y  -13 y^2

minimum was   1rep   x = -4   y = 3 disc 597 dSqrt 24
Automorph, written on right of Gram matrix:
-5872  5187
4389  -3877
for   Pari/gp: rt =  [ -5872 , 4389 ; 5187 , -3877 ] ;    h =  [ 22 , 5 ; 5 , -26 ] ;    r =  [ -5872 , 5187 ; 4389 , -3877 ] ;

opposite Pari/gp: rt =  [ -392 , 293 ; -293 , 219 ] ;    h =  [ 22 , 5 ; 5 , -26 ] ;    r =  [ -392 , -293 ; 293 , 219 ] ;

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ • Do you prefer C++ to Java? – user2661923 Apr 14 at 17:29 • @user2661923 I am told by reliable sources that Java is better unless the only concern is speed. However, when I came back to town decades ago, they let me audit a self-paced course in C++, so that is the one I know. – Will Jagy Apr 14 at 18:41 • @user2661923 meanwhile, if you are interested in programming this, it is all integer arithmetic. Everything needed is in zakuski.utsa.edu/~jagy/indefinite_binary_Buell.pdf with this addition: the definition of "reduced" for indefinite$ax^2 + bxy + cy^2$is equivalent to:$ ac < 0 \; , \; \; \; b > |a+c| $– Will Jagy Apr 14 at 19:10 • I deleted my last comment, which I posted before examining the ...Buell pdf that you linked to. That answers all my questions, except 1. Do you have an opinion on the C++ facilities of large integers versus the Java facilities, which refer to Java's BigInteger class, which is mentioned here? – user2661923 Apr 14 at 19:23 • @user2661923 No opinion. Note Pell$u^2 - Dv^2=1$leads to an automrphiosm matrix$ A = \left( \begin{array}{cc} u & Dv \\ v & u \end{array} \right) $such that$A^T H A= H \; , \; \;$where$H$is the Hessian matrix of the form. The matrix my program reports as an "automorph" solves$A^T H A= H \; , \; \;$where this$H$is the Hessian of$11x^2 + 5xy - 13 y^2 $That is, the left column of this$A$represents$11$and the right column$ \; \;-13\$ – Will Jagy Apr 14 at 19:30