Tricks to find a closed form $x_n$ of recurrence relation $x_{n+1} = \frac{1}{1+x_n}$ where $x_1 = a > 0$, $n \in \mathbb N$ With the help of you guys I've been able to learn how to solve various recurrence equations, but today I came across one I couldn't handle:

Find a closed form of the sequence $\{x_n\}$ of recurrence relation (where $n \in \mathbb N$): 
  $$
\begin{cases} x_1 = a > 0\\x_{n+1} = \dfrac{1}{1+x_n}\end{cases}
$$ 

I've already made several attempts which include:


*

*Trying to infer the pattern by expanding the continuous fraction from bottom up. No result

*Expressing $x_{n+2}$ and multiply/add/subtract/divide expressions for $x_{n+1}$ and $x_{n+2}$. No result

*Suppose that $x_{n}$ has a rational form $k_n \over p_n$ and playing with the equations in different ways. No result


I believe there should be some clever trick to untangle this, but apparently i'm too dumb to see it.
The answer is known to be a fraction involving the Golden Ratio $\frac{\sqrt5 - 1}{2}$ so maybe this may help. 
Update
Using @AnotherJohnDoe's hint we may perform the following transformation:
Let $x_n = \frac{t_n}{t_{n+1}}$, then:
$$
\frac{t_{n+1}}{t_{n+2}} = \frac{1}{1+\frac{t_n}{t_{n+1}}} = \frac{t_{n+1}}{t_n + t_{n+1}}
$$
Which defines a recurrence relation in terms of $t$:
$$
t_{n+2} - t_{n+1} - t_n = 0
$$
The characteristic equation for this recurrence has two root so the closed form of $\{t_n\}$ is:
$$
t_n = C_1\cdot\left({1+\sqrt5\over 2}\right)^n + C_2 \cdot \left({1-\sqrt5 \over 2}\right)^n
$$
Let $\phi_1 = \frac{1+\sqrt5}{2}$ and $\phi_2 = \frac{1-\sqrt5}{2}$:
$$
t_n = C_1\cdot \phi_1^n + C_2\cdot\phi_2^n \\
t_{n+1} = C_1\cdot \phi_1^{n+1} + C_2\cdot\phi_2^{n+1}
$$
Then:
$$
x_n = \frac{t_n}{t_{n+1}} \\
x_n = \frac{C_1\cdot \phi_1^n + C_2\cdot\phi_2^n}{C_1\cdot \phi_1^{n+1} + C_2\cdot\phi_2^{n+1}}
$$
So using the initial conditions $x_1 = a$ and $x_2 = {1\over 1+a}$:
$$
\begin{align}
a &= \frac{C_1\cdot \phi_1 + C_2\cdot\phi_2}{C_1\cdot \phi_1^2 + C_2\cdot\phi_2^2} \\
{1\over 1+a} &= \frac{C_1\cdot \phi_1^2 + C_2\cdot\phi_2^2}{C_1\cdot \phi_1^3 + C_2\cdot\phi_2^3}
\end{align}
$$
But this system doesn't seem to have solutions.

When stuck, there's always the option of computing the first few terms of the sequence, to see if a pattern appears.

Computing the first $6$ terms, we get
\begin{align*}
x_1&=a\\[4pt]
x_2&=\frac{1}{1+a}\\[4pt]
x_3&=\frac{1+a}{2+a}\\[4pt]
x_4&=\frac{2+a}{3+2a}\\[4pt]
x_5&=\frac{3+2a}{5+3a}\\[4pt]
x_6&=\frac{5+3a}{8+5a}\\[4pt]
\end{align*}
so it appears to be the case that
$$x_n=\frac{F_{n-1}+aF_{n-2}}{F_n+aF_{n-1}}$$
where $F_n$ is the $n$-th Fibonacci number (using $F_{-1}=1$ and $F_{0}=0$).

The proof by induction is straightforward . . .

For $n=1$, we have 
$$\frac{F_0+aF_{-1}}{F_1+aF_0}=\frac{a}{1}=a=x_1$$
so the base case is verified.

Suppose the claim holds for some positive integer $n$.$\;$Then
\begin{align*}
x_{n+1}&=\frac{1}{1+x_n}\\[4pt]
&=\frac{1}{1+{\Large{\frac{F_{n-1}+aF_{n-2}}{F_n+aF_{n-1}}}}}\\[4pt]
&=\frac{F_n+aF_{n-1}}{(F_{n-1}+F_n)+a(F_{n-2}+F_{n-1})}\\[4pt]
&=\frac{F_n+aF_{n-1}}{F_{n+1}+aF_n}\\[4pt]
\end{align*}
which completes the induction.
