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. 
 A: 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}.$
A: 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}$.
A: 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}
