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

  • $\begingroup$ This is merely an outline; if you need help filling in details, let me know $\endgroup$ 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}

  • $\begingroup$ 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. $\endgroup$
    – lEm
    Dec 29 '19 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.