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

Solution 1:

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

Solution 2:

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

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