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

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?

• i really dont know why this got downvoted .. so sad !! i think the question is really nice (+1) Dec 5 '18 at 16:20
• @AhmadBazzi neither do I but thanks for the encouraging comment and upvote! :) Dec 5 '18 at 16:21

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

• Thanks. Very nice solution (+1). Interesting property of $f(x)$ and clever application. Dec 5 '18 at 17:02

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

• Thanks (+1). Nice hint. At least that gets us to a nice linear recurrence relation. Dec 5 '18 at 16:55
• clever substitution (+1) Dec 5 '18 at 17:31

[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}

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

• Thanks. If a series $c_n$ converges to $\phi$ as $n\to \infty$, can it be concluded that $c_n=\frac {F_n}{F_{n+1}}$, since we know that $\lim_{n\to\infty}\frac {F_n}{F_{n+1}}=\phi$, or is this not necessarily the case? Dec 6 '18 at 6:25
• That is definitely not always true. For example, each of the series $c_n = \dfrac{F_n-1}{F_{n+1}}$, $d_n = \dfrac{F_{n+1}}{F_{n+2}}$, $e_n = \dfrac{F_n}{F_{n+1}-1000}$, and $f_n = \sqrt{\dfrac{F_n}{F_{n+2}}}$ converges to $\phi = \dfrac{\sqrt{5}-1}{2}$. There are also many series which converge to $\phi$ which aren't expressible in "nice" closed forms. Dec 6 '18 at 6:31