# Relation between two rational sequences approximating square root 2

We define recursive sequences $$a_{n+1}=1+\frac 1{1+a_n}$$, $$a_1=1$$ and $$b_{n+1}=\frac{b_n^2+2}{2b_n}$$, $$b_1=1$$. I wish to show that $$b_{n+1}=a_{2^n}$$.

This can be proven using closed forms expressions related to continued fractions. I know that $$a_n$$ can be expressed as $$a_n=\sqrt2\cdot \frac{(1+\sqrt 2)^n +(1-\sqrt 2)^n}{(1+\sqrt 2)^n - (1-\sqrt 2)^n}$$

On the other hand, we can prove inductively that $$\frac{b_{n+1}-\sqrt 2}{b_{n+1}+\sqrt 2}=\left(\frac{1-\sqrt 2}{1+\sqrt 2}\right)^{2^n}$$

So the relation $$a_{2^n}=b_{n+1}$$ can be deduced by expanding the fractions. However the computation is rather tedious, I am looking for a proof that does not involve expanding everything into closed form expressions. Thanks.

Define the sequences $$\,a_n := c_n/d_n\,$$ where $$\,c\,$$ and $$\,d\,$$ are OEIS sequences A001333 and A000129. Consider the matrix $$M := \begin{pmatrix} 1 & 1 \\ 2 & 1 \end{pmatrix} \tag{1}$$ whose powers are $$M^n = \begin{pmatrix} c_n & d_n \\ 2d_n & c_n \end{pmatrix}. \tag{2}$$ Since $$\,M^{n+1} = M^n\, M\,$$ this explains the $$\,a_n\,$$ recursion.

Notice the algebraic matrix identity $$\begin{pmatrix} c & d \\ 2d & c \end{pmatrix}^2 = \begin{pmatrix} c^2+2d^2 & 2cd \\ 4cd & c^2+2d^2 \end{pmatrix}. \tag{3}$$ Since $$\,M^{2^{n+1}} = (M^{2^n})^2,\,$$ this explains the $$\,a_{2^n}\,$$ recursion.

Note that the matrix $$\,M\,$$ is equivalent to $$\,m:=1\pm\sqrt{2}.\,$$ Thus equation $$(2)$$ is equivalent to $$\,m^n = c_n\pm d_n\sqrt{2}\,$$ and equation $$(3)$$ is equivalent to $$\,(c\pm d\sqrt{2})^2 = (c^2+2d^2)\pm(2cd)\sqrt{2}.$$

Here is an outline of a proof by induction that doesn't use the closed form expressions.

We are given $$a_{n+1}=\dfrac{2+a_n}{1+a_n}$$ and $$a_1=1$$.

First prove by induction on $$m$$ that $$a_{n+m}=\dfrac{2+a_ma_n}{a_m+a_n}.$$

It follows that $$a_{2n}=\dfrac{2+a_n^2}{2a_n}$$.

Now prove by induction that $$b_{n+1}=a_{2^n}$$.

• This is merely an outline; if you need help filling in details, let me know Dec 29 '19 at 21:16

Let $$\left(\frac{1-\sqrt 2}{1+\sqrt 2}\right)^{2^n} = t$$ for simplicity. Then, $$\frac{b_{n+1}-\sqrt 2}{b_{n+1}+\sqrt 2} = t$$ implies \begin{align} b_{n+1} &= \sqrt 2 \frac{1+t}{1-t} \\ &=\sqrt2 \frac{(1+\sqrt 2)^{2^n} +(1-\sqrt 2)^{2^n}}{(1+\sqrt 2)^{2^n} - (1-\sqrt 2)^{2^n}}\\ &= a_{2^n} \end{align}

• I already figured this out. I'm sorry if I didn't make myself clear in the question. I was looking for a proof perhaps by induction or any less "brute force", because the question (I got from my friend) was from some mathematics olympiad contest, which led me to believe there is a more clever proof.
– lEm
Dec 29 '19 at 17:39