Connecting Greek Ladders and Continued Fractions - Matching Continued Fraction Convergents to Greek Ladder Approximations

As we noted earlier, the simple continued fraction converging to \(\sqrt{2}\) is \([1,2,2,2 \dots]\). It is easy to check that the \(n\)th convergent of this continued fraction is equal to the value of \(\frac{y_n}{x_n}\) produced by the classic Greek ladder for \(\sqrt{2}\) by hand (or computer) up to any \(n\) we wish. A general proof for all \(n\) is left to the reader but we should note that the proof is a special case of the induction proof we will demonstrate later in this section. Similarly, the simple continued fraction converging to \(\sqrt{3}\) is \([1,1,2,1,2,1,2,\dots]\) and the sequence of convergents of this continued fraction is equal to the sequence of rational numbers produced by the classic Greek ladder for \(\sqrt{3}\). We might expect this relationship to continue for \(\sqrt{k}\) for any positive integer \(k,\) but when \(k = 5\) we see the simple continued fraction that converges to \(\sqrt{5}\) is \([2,4,4,4,4\dots],\) which produces convergents \[S_1 = 2,\ S_2 = \frac{9}{4}=2.25,\ S_3=\frac{38}{17}=2.23529,\ S_4=\frac{161}{72}=2.23611,\ \dots.\] However, the classic Greek ladder approximating \(\sqrt{5}\) is:

For \(k \ge 5\) we know that the first convergent of the simple continued fraction for \(\sqrt{k}\) is at least \(2,\) whereas the classic Greek ladder always start with \(1\). The reader is encouraged to investigate and attempt to prove that even adjusting the starting values of the Greek ladder so that \(y_1/x_1 = S_1\) will not make the two sequences equal.

The question we pose is, "can we find a continued fraction converging to \(\sqrt{k}\) such that the sequence of convergents is identical to the sequence of approximations that comes from the classic Greek ladder for all \(k \ge 2\)?" The answer to our question is, "yes." However, the continued fraction in question will not be a simple continued fraction. For example, \([1;4,2;4,2;4,2;\dots]\) is a continued fraction that converges to \(\sqrt{5}\) and the sequence of convergents of this continued fraction is equal to the sequence \(\frac{y_n}{x_n}\) created by the classic Greek ladder for \(\sqrt{5}\).

Claim:  We claim that the sequence of approximations created by the classic Greek ladder for \(\sqrt{k}\) is identical to the convergents of the continued fraction

\[[1; k-1,2;k-1,2;k-1,2;\dots].\]

The proof will proceed by induction; however, the induction argument is somewhat more sophisticated than standard induction proofs that establish common identities such as

\[1+2+\cdots+n = \frac{(n)(n+1)}{2}\]

for all positive integers \(n.\)

We believe that students who have had some experience with basic induction arguments will find it enlightening to examine this proof. Such students might attempt this proof on their own before reading what follows. We believe this exercise will be useful as a project in an introductory proofs course or an introductory Combinatorics class studying recursion. For a more challenging project, instructors might require that students discover the continued fraction on their own. In this case, students will need to create several examples, look for patterns, and test conjectures before attempting a proof.

Proof of the claim:  We start with the classic Greek ladder for \(\sqrt{k}\):

Recall that \(x_n = x_{n-1} + y_{n-1}\) and \(y_n = kx_{n-1} + y_{n-1}\) for \(n \ge 2.\)

Now, consider the continued fraction:

\[1+\frac{k-1}{2+\frac{k-1}{2 + \frac{k-1}{2+\frac{k-1}{\vdots}}}}\]

For \(n = 1\), we have \(S_1 = 1 = \frac{y_1}{x_1}\).

For \(n=2\), we have \(S_2 = 1+\frac{k-1}{2} = \frac{k+1}{2} = \frac{y_2}{x_2}\).

This establishes the truth of our statement for \(n=1\) and \(n=2\) and hence the base cases for our induction argument. Before proceeding with the inductive step we take a moment to note something about the convergents of the continued fraction:

\[S_3-1 = \frac{k-1}{2+\frac{k-1}{2}}=\frac{k-1}{{S_2}+1}\]

\[S_4-1 = \frac{k-1}{2+\frac{k-1}{2 + \frac{k-1}{2}}}=\frac{k-1}{{S_3}+1}\]

\[\vdots\]

Following the discussion that led to Equation (1), we see that for \(n\ge3\) we have,

\[S_n-1 = \frac{k-1}{S_{n-1}+1}\quad{\rm{(Equation}}\,\,2).\]

Now, our induction hypothesis states that for \(n\ge3\) we assume that the \((n-1)\)th convergent of the continued fraction is equal to \(\frac{y_{n-1}}{x_{n-1}}\). That is, we assume that

\[S_{n-1} = \frac{y_{n-1}}{x_{n-1}}.\]

Then, from Equation (2) we have

\[S_n-1 = \frac{k-1}{S_{n-1}+1}\]

\[= \frac{k-1}{\frac{y_{n-1}}{x_{n-1}}+1}\]

\[= \frac{k-1}{\frac{x_{n-1}+y_{n-1}}{x_{n-1}}}\]

\[= \frac{(k-1)x_{n-1}}{x_{n-1}+y_{n-1}}.\]

Adding \(1\) to both sides of the equation yields

\[S_n = \frac{(k-1)x_{n-1}}{x_{n-1}+y_{n-1}}+1\]

\[= \frac{kx_{n-1}+y_{n-1}}{x_{n-1}+y_{n-1}}.\]

Recalling the recursive definitions of \(x_n\) and \(y_n\) we have

\[S_n = \frac{y_n}{x_n}.\]

We have shown for \(n\ge 3\) that if \({S_{n-1}}={\frac{y_{n-1}}{x_{n-1}}},\) then \(S_n=\frac{y_n}{x_n}\). This completes the proof by induction that \(S_n=\frac{y_n}{x_n}\) for all \(n\ge1.\)

The key step in the preceding proof was establishing the recursive relation in Equation (2). This relation is very similar to Equation (1). If students have seen the proof that \([1,2,2,\dots]\) converges to \(\sqrt{2}\), then they may be on the look-out for a similar sort of relation. The instructor will need to be ready to help students realize Equation (2) in order to keep them moving forward on the proof.