Vrftsjtryk

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?

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$:
$$
fcirc 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=fcirc fcirc dots circ fbig(1big),$$ 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_nend{bmatrix}=begin{bmatrix}1&1\1&2end{bmatrix}^{n-1}begin{bmatrix}1\0end{bmatrix}
=begin{bmatrix}0&1\1&1end{bmatrix}^{2(n-1)}begin{bmatrix}1\0end{bmatrix}
$$
Finally, recall that $begin{bmatrix}0&1\1&1end{bmatrix}$ is the "Fibonacci matrix" which satisfies
$$
begin{bmatrix}0&1\1&1end{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$.

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

[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 1atop 1 2right)left(b_{n}atop c_{n}right)
=left(1 1atop 1 2right)^2left(b_{n-1}atop c_{n-1}right)=cdots\\
&=left(1 1atop 1 2right)^nleft(b_1atop c_1right)\\
&=left(0 1atop 1 1right)^{2n}left(b_1atop c_1right)\\
&=left(F_{2n-1} F_{2n} atop F_{2n} F_{2n+1}right)left(1atop 1right)
&&scriptsize(a_1=1Rightarrow 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}}qquadblacksquare}
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=[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}}$.