How can I find an explicit expression for this recursively defined sequence? We define the sequence $(u_n)_{n=1}^\infty$by:$$u_{n+1}=1+\frac{1}{u_n}$$
How can I find the limit of this sequence as it goes to infinity?

By induction, I can prove that it is bounded above and below. I have also proved that $$u_{n+2}-u_n=\frac {u_n-u_{n-2}}{(1+u_n)(1+u_{n-2})}$$
Therefore, I can show that $\lim_{n\to\infty} u_{2n}$ and $\lim_{n\to\infty} u_{2n+1}$ exist. However, I am unable to find the limits themselves or a an explicit formula. How does one go around doing this? Are there any standard methods?
 A: the initial term $u_0$ can not be $-1$ or $0$, so if the
limit of $ u_n $ exist, then it is necessarily the limit $l$ is a positif 
root of the $l^2-l-1$, following it is $\frac{1+\sqrt{5}}{2}$.
A: The candidate limit value $\ell$, satisfying
$$
\ell=1+\frac{1}{\ell},
$$
with solutions $\ell=\frac{1}{2}(1\pm\sqrt{5}) $, suggests a relation with the Fibonacci sequence $\{F_n\}$. In fact, if you put
$$
u_n=\frac{F_{n+1}}{F_n},
$$
you have the recurrence relation
$$
u_{n+1}=\frac{F_{n+2}}{F_{n+1}}=\frac{F_{n+1}+F_n}{F_{n+1}}=1+\frac{1}{u_n}.
$$
Therefore, you can use all the information about the Fibonacci sequence. It is not necessary to repeat that here.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Leftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{u_{n + 1} = 1 + {1 \over u_{n}} = {u_{n} + 1 \over u_{n}}}\,,\qquad u_{1} \not= 0\tag{1}$.

Let's consider the pair of sequences $\ds{p_{n + 1} = p_{n} + q_{n}}$ and
$\ds{q_{n + 1} = p_{n}}$. Note que $\ds{p_{n}/q_{n}}$ satisfies $\pars{1}$.
With $\ds{r_{n} \equiv {p_{n} \choose q_{n}}}$ we note that $\ds{r_{n + 1} = \mathsf{A}r_{n}}$ such that $\ds{r_{n} = \mathsf{A}^{n - 1}r_{1}}$ where
\begin{align}
\mathsf{A} & =
\pars{\begin{array}{cc}\ds{1} & \ds{1} \\ \ds{1} &  \ds{0}\end{array}} =
\half\pars{\begin{array}{cc}\ds{1} & \ds{0} \\ \ds{0} &  \ds{1}\end{array}} +
\pars{\begin{array}{cc}\ds{0} & \ds{1} \\ \ds{1} &  \ds{0}\end{array}} +
\half\pars{\begin{array}{cc}\ds{1} & \ds{0} \\ \ds{0} &  \ds{-1}\end{array}} =
\half\,\sigma_{0} + \vec{a}\cdot\vec{\sigma}
\\[3mm] &
\sigma_{0}\quad \mbox{is the}\ identity\ matrix\ \mbox{and}\quad \vec{a} \equiv \hat{x} + \half\,\hat{z}
\end{align}
$\ds{\vec{\sigma}}$ is a Pauli Matrix Vector. Then, $\ds{r_{n} = \pars{\half\,\sigma_{0} + \vec{a}\cdot\vec{\sigma}}^{n - 1}r_{1}}$. Note that
$\ds{\vec{a}\cdot\vec{\sigma}} =
\pars{\begin{array}{cc}\ds{1/2} & \ds{1} \\ \ds{1} &  \ds{-1/2}\end{array}}$ and $\ds{\pars{\vec{a}\cdot\vec{\sigma}}^{2} = {5 \over 4}\,\sigma_{0}}$.

With the vectors
\begin{equation}
s_{-} \equiv {0 \choose 1}\quad\mbox{and}\quad s_{+} \equiv {1 \choose 0}\,,
\qquad
u_{n} =
{s_{+}^{\mathrm{T}}\pars{\sigma_{0}/2 + \vec{a}\cdot\vec{\sigma}}^{n - 1}r_{1} \over
s_{-}^{\mathrm{T}}\pars{\sigma_{0}/2 + \vec{a}\cdot\vec{\sigma}}^{n - 1}r_{1}}
\tag{2}
\end{equation}

We have to evaluate
$\ds{\pars{\sigma_{0}/2 + \vec{a}\cdot\vec{\sigma}}^{n - 1}}$. For this purpose,
lets consider
$\ds{\expo{\lambda\pars{\sigma_{0}/2 + \vec{a}\cdot\vec{\sigma}}} =
\expo{\lambda/2}\expo{\lambda\vec{a}\cdot\vec{\sigma}}}$. Note that $\ds{\expo{\lambda\vec{a}\cdot\vec{\sigma}}}$ satisfies

\begin{align}
&\pars{\totald[2]{}{\lambda} - {5 \over 4}}\expo{\lambda\vec{a}\cdot\vec{\sigma}} = 0
\quad\mbox{with}\quad
\left.\expo{\lambda\vec{a}\cdot\vec{\sigma}}\right\vert_{\ \lambda\ =\ 0} =
\sigma_{0}\,,\quad
\left.\totald{\expo{\lambda\vec{a}\cdot\vec{\sigma}}}{\lambda}\right\vert_{\ \lambda\ =\ 0} = \vec{a}\cdot\vec{\sigma}
\\[3mm] \imp\quad &\
\expo{\lambda\pars{\sigma_{0}/2 + \vec{a}\cdot\vec{\sigma}}}  =
\expo{\lambda/2}\cosh\pars{{\root{5} \over 2}\,\lambda}\sigma_{0} +
{2 \over \root{5}}\,
\expo{\lambda/2}\sinh\pars{{\root{5} \over 2}\,\lambda}\vec{a}\cdot\vec{\sigma}
\\[3mm] = &\
\half\pars{\sigma_{0} + {2 \over \root{5}}\,\vec{a}\cdot\vec{\sigma}}\exp\pars{\varphi\lambda} +
\half\pars{\sigma_{0} - {2 \over \root{5}}\,\vec{a}\cdot\vec{\sigma}}\exp\pars{\Phi\lambda}
\end{align}
where $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ and
$\ds{\Phi \equiv {1 \over \varphi} = {1 - \root{5} \over 2}}$ are the Golden Ratio and the Conjugated Golden Ratio, respectively.
Then,
\begin{align}
\pars{\half\,\sigma_{0} + \vec{a}\cdot\vec{\sigma}}^{n - 1} =
\half\pars{\sigma_{0} + {2 \over \root{5}}\,\vec{a}\cdot\vec{\sigma}}
\varphi^{n - 1} +
\half\pars{\sigma_{0} - {2 \over \root{5}}\,\vec{a}\cdot\vec{\sigma}}
\Phi^{n - 1}
\end{align}
With this expression and $\pars{2}$ we can get an $\underline{\mbox{explicit formula for}\ u_{n}}$ which is a cumbersome algebraic task.

However, the limit $\ds{n \to \infty}$ is somehow straightforward since
$\ds{\varphi > \Phi > 1}$. In addition
$$
\sigma_{0} + {2 \over \root{5}}\,\vec{a}\cdot\vec{\sigma} =
\pars{%
\begin{array}{cc}
\ds{1 + {1 \over \root{5}}} & \ds{2 \over \root{5}}
\\
\ds{2 \over \root{5}} & \ds{1 - {1 \over \root{5}}}
\end{array}}
$$

With expression $\pars{2}$ $\ds{\pars{~\mbox{note that}\ u_{1} \not= 0~}}$:
\begin{align}
\color{#f00}{\lim_{n \to \infty}u_{n}} & =
{\pars{1 \quad 0}\pars{\sigma_{0} + 2\,\vec{a}\cdot\vec{\sigma}/\root{5}}
\ds{{u_{1} \choose 1}}
\over
\pars{0 \quad 1}\pars{\sigma_{0} + 2\,\vec{a}\cdot\vec{\sigma}/\root{5}}
\ds{{u_{1} \choose 1}}} =
{2/\root{5} + \pars{1 + 1/\root{5}}u_{1}
\over
1 - 1/\root{5} + 2u_{1}/\root{5}}
\\[3mm] & =
\color{#f00}{{1 + \root{5} \over 2}} = \color{#f00}{\varphi}\,,\quad\forall\ u_{1} \not= 0
\end{align}
