# Continued fractions proof?

Let $b_1=1$ and $$b_n=1+\frac{1}{1+b_{n-1}}$$ for $n\ge 2$. Note that $b_n \ge 1$ for all $n$ in $\mathbb N$. ($\mathbb N$ represents the positive integers)

Show that $b_{2k-1}^2<2$ for all $k \in \mathbb N$.

Any ideas on how to start?

Thanks.

-

Let us try an inductive argument. For $b_1$ this certainly holds. Suppose the result holds for $b_{2n-1}$. Consider $$b_{2n+1} = 1+\frac{1}{1+b_{2n}} = 1+\frac{1}{2 + \frac{1}{1+b_{2n-1}}}$$ From the inductive hypothesis, we know that $b_{2n-1} < \sqrt{2}$ or equivalently $$b_{2n+1} < 1 + \frac{1}{2 + \frac{1}{1+\sqrt{2}}} = \frac{4+3\sqrt{2}}{3+2\sqrt{2}}$$ The latter expression is in fact $\sqrt{2}$ disguised. To see this, note that $$\frac{4+3\sqrt{2}}{3 + 2\sqrt{2}} - \sqrt{2} = \frac{4 + 3\sqrt{2} - 3\sqrt{2} - \sqrt{2}\sqrt{2}}{3 + 2\sqrt{2}} = 0$$

-
Thank you, that was very helpful. –  Alti Oct 14 '12 at 1:08

It’s clear that each $b_n$ is rational, so let $b_n=\dfrac{p_n}{q_n}$ for some integers $p_n$ and $q_n$. The recurrence is then

\begin{align*} b_{n+1}&=1+\frac1{1+b_n}\\ &=\frac{2+b_n}{1+b_n}\\ &=\frac{2+\frac{p_n}{q_n}}{1+\frac{p_n}{q_n}}\\ &=\frac{p_n+2q_n}{p_n+q_n}\;,\tag{1} \end{align*}

with $p_1=q_1=1$.

The sequence $\left\langle\dfrac{p_n}{q_n}:n\in\Bbb Z^+\right\rangle$ may be recognized from $(1)$ as the sequence of convergents of the continued fraction expansion of $\sqrt 2$, which is $[1;\overline{2}]$. This can also be seen directly from the original recurrence, as

$$1+\frac1{2+\frac1x}=1+\frac1{1+\left(1+\frac1x\right)}\;;\tag{2}$$

in particular, if $1+\frac1x$ is the $n$-th convergent to $\sqrt 2$, $(2)$ gives the $(n+1)$-st convergent, and we have $$b_{n+1}=1+\frac1{1+b_n}\;.$$

General facts about continued fractions ensure that the convergents are alternately less than and greater than $\sqrt 2$, and since $b_1<\sqrt2$, it is the odd-indexed convergents that are less than $\sqrt 2$.

-
Thank you very much –  Alti Oct 14 '12 at 1:09

Put another way, each convergent $\frac{x_n}{y_n}$ appears as numerator and denominator in the left-hand column of $$\left( \begin{array}{rr} 1 & 2 \\ 1 & 1 \end{array} \right)^n,$$ as in $$\left( \begin{array}{rr} 1 & 2 \\ 1 & 1 \end{array} \right)^2 \; = \; \left( \begin{array}{rr} 3 & 4 \\ 2 & 3 \end{array} \right),$$ then $$\left( \begin{array}{rr} 1 & 2 \\ 1 & 1 \end{array} \right)^3 \; = \; \left( \begin{array}{rr} 7 & 10 \\ 5 & 7 \end{array} \right),$$ and $$\left( \begin{array}{rr} 1 & 2 \\ 1 & 1 \end{array} \right)^4 \; = \; \left( \begin{array}{rr} 17 & 24 \\ 12 & 17 \end{array} \right),$$

and so on.

And so we get $$x_n^2 \,- \, 2 \, y_n^2 \, = (-1)^n,$$ because $$\left( \begin{array}{rr} 1 & 2 \\ 1 & 1 \end{array} \right)^n \; = \; \left( \begin{array}{rr} x_n & 2 y_n \\ y_n & x_n \end{array} \right)$$ and we are comparing determinants.

-
Thank you for your help –  Alti Oct 14 '12 at 1:09