Formula using fibonacci numbers Let $a_n$ be the $n^{th}$ term of the sequence defined recursively by
 $a_{n+1} = \frac {1}{1+a_n}$
and let $a_1 = 1.$ Find a formula for $a_n$ in terms of the Fibonacci numbers $F_n$. Prove that the formula you found is valid for all natural numbers $n.$ 
Wow can I solve this type of problem?
And, how to prove it by induction? Do i solve for $a_n$ or what? I'm new to this chaper( sequences and series).
 A: If I see a recurrence relation where $a_{n+1}$ depends on $a_n$ as a linear fraction. I will write $a_n$ as a ratio $\frac{p_n}{q_n}$ for two other sequences $(p_n)$ and $(q_n)$ to be determined. Simplify the relation and see what I can get.
For the recurrence relation at hand, we have
$$\frac{p_{n+1}}{q_{n+1}} = a_{n+1} = \frac{1}{1+a_n} = \frac{q_n}{q_n + p_n}$$
If the two sequences $(p_n)$, $(q_n)$ satisfies
$$\begin{cases}
p_{n+1} &= q_n\\
q_{n+1} &= q_n + p_n
\end{cases}
\quad\implies\quad
\begin{cases}
p_{n+1} &= q_n\\
q_{n+1} &= q_n + q_{n-1}
\end{cases},
\quad\text{ for }n > 1
$$
then $\frac{p_n}{q_n}$ will be a solution of original recurrence relation.
Notice the recurrence relation for $q_n$ is the one for Fiboniacci numbers.
One should be able to express $q_n$ and hence $p_n$ in terms of Fibonacci numbers. Since $a_1 = 1$, we can take 
$$p_1 = q_1 = 1 \quad\iff\quad q_0 = q_1 = 1$$ 
Now $F_1 = F_2 = 1$, it suggest us to pick
$$\begin{cases}p_n &= F_n,\\ q_n &= F_{n+1}\end{cases}
\quad\iff\quad
a_n = \frac{F_n}{F_{n+1}}
$$
Up to this point, we haven't proved $a_n$ is given by above expression. We only have an ansatz of what $a_n$ should be. By direct subsitution, we can verify
this ansatz do satisfy the original recurrence relation.
$$a_1 = \frac{F_1}{F_2} = 1\quad\text{ and }\quad 
a_{n+1} = \frac{F_{n+1}}{F_{n+2}} = \frac{F_{n+1}}{F_{n+1} + F_{n}} = \frac{1}{1 + \frac{F_n}{F_{n+1}}} = \frac{1}{1 + a_n}$$
A: By induction $a_n=\frac{F_n}{F_{n+1}}$ because $a_1=\frac{F_1}{F_2}=1$ and
$$a_{n+1}=\frac{1}{1+a_n}=\frac{1}{1+\frac{F_n}{F_{n+1}}}=\frac{F_{n+1}}{F_{n+2}}.$$
$\{F_n\}:1,1,2,3,5,...$.
