Prove $a_n=1+\frac{a_{n-1}}{1+a_{n-1}}$ increasing There is a homework question in Calculus-1 course:
Calculate the limit of $\{a_n\}$: $$a_1=1,\ a_n=1+\frac{a_{n-1}}{1+a_{n-1}}$$
I think the key points are bounded and increasing, and I have proved that $$a_n\in(1, 2)$$ 
If I knew it's increasing then $$a=1+\frac{a}{1+a}\Rightarrow\lim a_n=\frac{\sqrt5+1}{2}$$
My question is How to Prove it's increasing?
I tried it in two ways:
$$a_{n+1}-a_n=1+\frac{a_n}{1+a_n}-a_n=\frac{-a^2_n+a_n+1}{1+a_n}$$
But how to prove that $-a^2_n+a_n+1>0$?
Another way is
$$\frac{a_{n+1}}{a_n}=\frac{1}{a_n}+\frac{1}{1+a_n}=\frac{1+2a_n}{a_n+a^2_n}$$
But how to prove that $1+2a_n>a_n+a^2_n$?
This is not a proof question which means $\frac{\sqrt5+1}{2}$ is not a known result.
Thank you!
 A: First, we prove that $a_n$ is bounded above. Obviously, $a_n = 1+ \frac{a_{n-1}}{a_{n-1}+1} < 2$. 
To prove that the sequence is increasing, we can just use induction. The base cases are trivial so suppose the claim holds for all naturals $ \le k$. Then $a_{k+1}-a_k = \frac{a_k}{1+a_k} - \frac{a_{k-1}}{1+a_{k-1}} = \frac{a_k(1+a_{k-1})-a_{k-1}(1+a_k)}{(1+a_k)(1+a_{k-1})}$.
The numerator is $a_k-a_{k-1}$ which by the inductive  hypothesis is $> 0$ so we are done.
A: Consider the sequence 
\begin{align}
a_{n} = 1 + \frac{a_{n-1}}{1+a_{n-1}}
\end{align}
where $a_{1} = 1$.
Let $2 \alpha = 1 + \sqrt{5}$ and $2 \beta = 1-\sqrt{5}$. It is seen that $\alpha > \beta$ and $\beta^{n} \rightarrow 0$ as $n \rightarrow \infty$. Now, the terms of $a_{n}$ are $a_{n} \in \{ 1, 3/2, 8/5, \cdots \}$ which are seen to be the Fibonacci numbers, and in general
\begin{align}
a_{n} = \frac{F_{2n}}{F_{2n-1}}.
\end{align}
Since $\sqrt{5} F_{n} = \alpha^{n} - \beta^{n}$ then
\begin{align}
a_{n} = \frac{\alpha^{2n} - \beta^{2n}}{\alpha^{2n-1} - \beta^{2n-1}} = \alpha \ \frac{1 - \left(\frac{\beta}{\alpha} \right)^{2n}}{1 - \left(\frac{\beta}{\alpha} \right)^{2n-1}} .
\end{align}
Taking the limit as $n \rightarrow \infty$ leads to
\begin{align}
\lim_{n \rightarrow \infty} a_{n} = \alpha = \frac{1+\sqrt{5}}{2}.
\end{align}
