# 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?

• $u_\infty=1+\dfrac 1{u_\infty}$. This is a quadratic equation but only the one which falls in the bound you have proved is the real limit. Commented Jun 12, 2016 at 17:01
• Suppose $\lim u_n=L$. What is $\lim u_{n+1}$? Commented Jun 12, 2016 at 17:01
• At convergence, there is no difference anymore between $u_{n+1}$ and $u_n$. What can you conclude ?
– user65203
Commented Jun 12, 2016 at 17:02
• I had never thought of that, it is such a beautiful idea
– GuPe
Commented Jun 12, 2016 at 18:59

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.

• I really like how you offered an additional relationship with other well known sequences. Commented Jun 12, 2016 at 22:44
• The OP did not show that $u_n$ has a limit, but by relating $u_{k+2}$ to $u_k$, a similar argument shows that $u_{2n}$ and $u_{2n+1}$ both converge to a solution of the same equation.
– user14972
Commented Jun 13, 2016 at 0:30
• Very nice (+1). If you had not guessed the relationship with the Fibonacci sequence from the limit, how would you have derived it using only the recurrence relation provided? Commented Jun 13, 2016 at 17:09
• Well, if I hadn't noted the appearance of the golden ratio, I think I wouldn't have thought to the Fibonacci numbers at all. Unfortunately I cannot provide any general advice. Maybe I can only make a remark about some vague similarity with the differential equations case. Here, from a linear second order (i.e involving $n$, $n+1$, $n+2$) recurrence relation (the one of the Fibonacci numbers), we can obtain a non-linear first order recurrence relation. Similarly, from a second order linear differential equations, one can obtain an equivalent first order non linear equation: the Riccati equation Commented Jun 13, 2016 at 17:55

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

• What about $u_0 = (1 - \sqrt{5})/2$?
– user14972
Commented Jun 13, 2016 at 0:32
• the sequence is stationair $u_n=u_0$ Commented Jun 14, 2016 at 9:58

$\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 $$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}$$
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}