Recurrence and Fibonacci: $a_{n+1}=\frac {1+a_n}{2+a_n}$

Question

For the recurrence relation $$a_{n+1}=\frac {1+a_n}{2+a_n}$$ where $a_1=1$, the solution is $a_n=\frac {F_{2n}}{F_{2n+1}}$, where $F_n$ is the $n$-th Fibonacci number, according to the convention where $F_1=0, F_2=1,\cdots $

This can easily be proven by substituting the solution back into the recurrence relation, or alternatively by induction.

Can the solution be derived directly from the recurrence relation itself, i.e. not by substituting the solution into the recurrence, or by induction?

Answer 1

Yes, it can be derived directly, assuming some familiarity with the Fibonacci numbers. I am using the initial conditions $F_1=F_2=1$ for the Fibonacci numbers, which impies that $$ a_{n}=\frac{F_{2n-1}}{F_{2n}} $$

There is a nice property involving functions of the form $$ f(x) = \frac{ax+b}{cx+d} $$ If you compose such an $f$ with another $g(x)=\frac{px+q}{sx+t}$ of the same form, the result is another function in the same form, whose coefficients are identical to matrix product of the squares of coefficients of $f$ and $g$: $$ f\circ g = \frac{(ap+bs)x+(aq+bt)}{(cp+ds)x+(cq+dt)} $$ Letting $$ f(x)=\frac{1+x}{2+x} $$ this implies that $$a_n=f\circ f\circ \dots \circ f\big(1\big),$$ with $n-1$ functions composed. Using the matrix connection, and the observation that substituting $x=1$ results in a fraction whose numerator and denominator are the components of the right column of this matrix, this implies that $a_n$ is a fraction whose numerator an denominator are given by the matrix $$ a_n=\frac{b_n}{c_n},\qquad \begin{bmatrix}b_n\\c_n\end{bmatrix}=\begin{bmatrix}1&1\\1&2\end{bmatrix}^{n-1}\begin{bmatrix}1\\0\end{bmatrix} =\begin{bmatrix}0&1\\1&1\end{bmatrix}^{2(n-1)}\begin{bmatrix}1\\0\end{bmatrix} $$ Finally, recall that $\begin{bmatrix}0&1\\1&1\end{bmatrix}$ is the "Fibonacci matrix" which satisfies $$ \begin{bmatrix}0&1\\1&1\end{bmatrix}^n=\begin{bmatrix}F_{n-1}&F_n\\F_{n}&F_{n+1}\end{bmatrix}, $$ an identity which follows directly from the recurrence $F_n=F_{n-1}+F_{n-2}$ and base cases $F_0=0,F_1=1$.

Answer 2

Hint: By letting $2+a_n=\frac{b_{n+1}}{b_n}$, we get $$\frac{b_{n+2}}{b_{n+1}}-2 = 1 - \frac{b_{n}}{b_{n+1}} \implies b_{n+2} -3b_{n+1} + b_{n} = 0.$$

Answer 3

[My interpretation of Mike Earnest's solution, posted here for my own reference only]

$$\begin{align} a_{n+1}&=\frac {b_{n+1}}{c_{n+1}}=\frac {1+\frac {b_n}{c_n}}{2+\frac {b_n}{c_n}}=\frac {b_n+c_n}{b_n+2c_n}\\\\ \left(b_{n+1}\atop c_{n+1}\right) &=\left(1\ \ 1\atop 1\ \ 2\right)\left(b_{n}\atop c_{n}\right) =\left(1\ \ 1\atop 1\ \ 2\right)^2\left(b_{n-1}\atop c_{n-1}\right)=\cdots\\\\ &=\left(1\ \ 1\atop 1\ \ 2\right)^n\left(b_1\atop c_1\right)\\\\ &=\left(0\ \ 1\atop 1\ \ 1\right)^{2n}\left(b_1\atop c_1\right)\\\\ &=\left(F_{2n-1}\ \ F_{2n}\ \ \ \atop F_{2n}\ \ \ \ F_{2n+1}\right)\left(1\atop 1\right) &&\scriptsize(a_1=1\Rightarrow b_1=1, c_1=1)\\\\ &=\left(F_{2n-1}+F_{2n}\ \ \ \atop F_{2n}\ \ \ +F_{2n+1}\right)\\\\ &=\left(F_{2n+1}\atop F_{2n+2}\right)\\\\ \therefore a_{n+1}&=\frac {b_{n+1}}{c_{n+1}}=\frac {F_{2n+1}}{F_{2n+2}}\\\\ \color{red}{a_n}&\color{red}{=\frac {F_{2n}\ \ \ }{F_{2n+1}}\qquad\blacksquare} \end{align}$$

Answer 4

Let $b_n=\frac{1}{a_n}$. We have $$ b_n = \frac{a_n+2}{a_n+1} = \frac{2b_n+1}{b_n+1}=1+\frac{1}{1+\frac{1}{b_n}} $$ hence in terms of continued fractions we have $b_1=[1], b_2=[1;1,1], b_3=[1;1,1,1,1]$ and so on. The convergents of $\varphi=\frac{1+\sqrt{5}}{2}=[1;\overline{1}]$ are given by ratios of consecutive Fibonacci numbers, hence $b_n=\frac{F_{2n-1}}{F_{2n+1}}$ and $a_n=\frac{F_{2n}}{F_{2n+1}}$.