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

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

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