# Proving the continued fraction representation of $\sqrt{2}$

There's a question in Spivak's Calculus (I don't happen to have the question number in front of me in the 2nd Edition, it's Chapter 21, Problem 7) that develops the concept of continued fraction, specifically the continued fraction representation of $\sqrt{2}$. Having only recently become aware of continued fractions, I'm trying to work my way through this problem, but I'm stuck at the very last stage.

Here's what I've got so far: Let $\{a_n\}$ be the sequence defined recursively as $$a_1 = 1, a_{n + 1} = 1 + \frac{1}{1 + a_n}$$ Consider the two subsequences $\{a_{2n}\}$ and $\{a_{2n - 1}\}$. I've already shown that $\{a_{2n}\}$ is monotonic, strictly decreasing, and bounded below by $\sqrt{2}$, and similarly I've shown that $\{a_{2n - 1}\}$ is monotonic, strictly increasing, and bounded above by $\sqrt{2}$. Obviously, both of these subsequences converge.

Although of course in general, if two subsequences of a sequence happen to converge to the same value, that doesn't guarantee that the sequence itself converges at all (much less to that same value), in the case where the subsequences are $\{a_{2n}\}$ and $\{a_{2n - 1}\}$, it's easy to show that if they both converge to the same value, then so will $\{a_n\}$ (since every term of $\{a_n\}$ is a term of one of the two subsequences). So no problem there.

In other words, it remains only to show that not only do the subsequences converge, but they converge to $\sqrt{2}$ in particular. Take, for starters, $\{a_{2n - 1}\}$ (if I can get $\{a_{2n - 1}\}$ to converge to $\sqrt{2}$, I'm sure getting $\{a_{2n}\}$ to converge to $\sqrt{2}$ won't be very different). Because it's strictly increasing and bounded above by $\sqrt{2}$, it converges to some number $x \leq \sqrt{2}$. Suppose that $x < \sqrt{2}$. We want to show this doesn't happen.

But this is where I'm getting stuck. I feel like I want to take $\epsilon = \sqrt{2} - x$ and show that there exists some $N$ such that $a_{2N - 1} > x$, which would finish the problem due to the monotonicity of $\{a_{2n - 1}\}$. But this isn't working.

Any hints? Thanks a ton.

-

You have shown that the sequence of $a_{2n}$ converges. Call $e$ (for even) its limit, and call $o$ the limit of $a_{2n+1}$. Then the recursive relation giving $a_{n+1}$ in terms of $a_n$ implies that $$e=1+1/(1+o)$$ and $$o=1+1/(1+e),$$ from which it follows that $e=o=\sqrt2$.

[For example, take the limit as $n\to\infty$ of $a_{2n}=1+1/(1+a_{2n-1})$ to get the first relation, and similarly you get the second exchanging odd and even. From the first equation, you get $2+o=e+eo$ and from the second $2+e=o+oe$. Subtracting, you get $o-e=e-o$, so $o=e$. From the first equation, you now get $2=o^2$.]

-

As I explained in a previous similar question, one can use the Banach fixed point theorem to solve these kinds of problems. For the special case of iterating a fractional linear transformation you can also (as I think is also explained in answers to that question) write down an explicit closed form for the $n^{th}$ term by diagonalizing a $2 \times 2$ matrix.

-
Short version of Qiaochu's answer: CF expansions of quadratic surds are easily established by either appealing to Banach or diagonalizing an appropriate matrix. – J. M. Dec 17 '10 at 2:49

I don't think you need to break it up into two cases. In stead we can do this:

1. Establish that the sequence $\langle a_i \rangle$ is cauchy and therefore convergent to some $L$. For this establish the sequence $\langle f^i(0)\rangle$ converges to zero, where $f^i$ is the 'i'th iterate of $\frac{1}{2+x}$.
2. Notice that the relation: $a_{n+1}=1+\frac{1}{1+a_n}$ is the same as $a_{n+1}a_n + a_{n+1} - a_n -2 = 0$.
3. Take limits at both ends to get: $L^2+L-L-2=0$.
-