# Limit of a recursive sequence with $u_n$

It is given that $u_{n+1} =1+\dfrac{1}{u_n}$ and $u_1 =1$. Find the limit of $u_n$ as $n\to\infty$.

The limit is $\frac{\sqrt{5}+1}{2}$ from a calculator. Is there an algebraic way to determine this? You can also determine that sequence is bounded but not monotonic.

• If $u_1=0$ then $u_2$ is not defined ... division by $0$ are bad. – wece May 18 '13 at 12:49
• Fixed it...its supposed to be 1 – Eddy May 18 '13 at 12:51
• If $\lim_{n\to\infty}u_n\to c>0,\lim_{n\to\infty}c=1+\frac1c.$ Solve for $c>0$ – lab bhattacharjee May 18 '13 at 13:04

If you want to be rigorous you should proove that the limit exists.

You can do that showing that the odd terms form a decreasing sequence while the even terms form an increasing sequence (induction). Then show that those sequences are bounded below/above.

Writing $u_n$ as $\frac{p_n}{q_n}$ for two sequences $(p_n)$, $(q_n)$ to be determined. We have:

$$u_{n+1} = 1 + \frac{1}{u_n} \iff \frac{p_{n+1}}{q_{n+1}} = 1 + \frac{q_n}{p_n} = \frac{p_n+q_n}{p_n}$$ Normalize $(p_n)$ and $(q_n)$ appropriately, we can turn the non-linear recurrence equation into a linear one:

$$\begin{pmatrix}p_{n+1}\\q_{n+1}\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}p_n\\q_n\end{pmatrix}$$ The charateristic polynomial of the matrix $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ is equal to:

$$\lambda (\lambda - 1 ) - 1^2 = \lambda^2 - \lambda - 1 = (\lambda - \varphi)(\lambda + \varphi^{-1})$$ where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. The matrix has eigenvalues $\varphi$ and $-\varphi^{-1}$ with corresponding eigenvectors:

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}\varphi\\1\end{pmatrix} = \varphi \begin{pmatrix}\varphi\\1\end{pmatrix} \quad\text{ and }\quad \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}-\varphi^{-1}\\1\end{pmatrix} = -\varphi^{-1}\begin{pmatrix}-\varphi^{-1}\\1\end{pmatrix}$$ Since $u_1 = 1$, we will choose $p_1 = q_1 = 1$. Expressing $\begin{pmatrix}1\\1\end{pmatrix}$ in terms of the eigenvectors:

$$\begin{pmatrix}1\\1\end{pmatrix} = \alpha \begin{pmatrix}\varphi\\1\end{pmatrix} + \beta \begin{pmatrix}-\varphi^{-1}\\1\end{pmatrix} \implies \alpha = \frac{\varphi+1}{\varphi+2} \;\text{ and }\; \beta = \frac{1}{\varphi+2}$$ We get $$\begin{pmatrix}p_n\\q_n\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n-1} \begin{pmatrix}p_1\\q_1\end{pmatrix} = \alpha \varphi^{n-1} \begin{pmatrix}\varphi\\1\end{pmatrix} + \beta (-\varphi^{-1})^{n-1}\begin{pmatrix}-\varphi^{-1}\\1\end{pmatrix}$$ This allow us to derive a closed form expression for $u_n$: $$u_n = \frac{p_n}{q_n} = \frac{\alpha \varphi^n + \beta (-\varphi^{-1})^n}{\alpha \varphi^{n-1} + \beta (-\varphi^{-1})^{n-1}} = \varphi \frac{\alpha + \beta (-\varphi^{-2})^n}{\alpha + \beta (-\varphi^{-2})^{n-1}}$$ Since $| -\varphi^{-2} | < 1$, this implies $\lim_{n\to\infty} u_n = \varphi \frac{\alpha + \beta*0}{\alpha + \beta*0} = \varphi$.

I just found out how to do it. Assume that the limit is equal to a. Therefore, the limit of u_n+1 and u_n are both equal to a. Using the recursive definition, place a back in to get. a=1+1/a which is equivalent to a^2-a-1=0. Solving for a gives two answers. But, since u_n is bounded between 1 and 2; (1+sqrt(5))/2 is the accepted limit.

• You have only shown that the limit is $(1+\sqrt{5})/2$ provided it exists. – egreg May 18 '13 at 12:57
• That is true... – Eddy May 18 '13 at 13:04
• Amire Bendjeddou's technique is very good for solving the problem. – egreg May 18 '13 at 13:10
• Is there any theorem that states that a bounded sequence which increases for even and decreases for odd is convergent. – Eddy May 18 '13 at 13:13
• @Eddy : No, because that is false. In your problem, then the even terms converge and the odd terms converge and the limits(s) satisfy $c = 1 +\frac{1}{c},\ c > 0$ so the limit(s) are the same. – Stefan Smith May 18 '13 at 15:39

If you are only interested in finding the limit, then here is an algebraic way to find it. Assume

$$\lim_{n\to \infty} u_n = a \implies \lim_{n\to \infty} u_{n+1} = \lim _{n\to \infty }(1+\frac{1}{u_n}) \implies a = 1+\frac{1}{a}\implies a^2-a-1=0$$

$$\implies a = \dots\,.$$

Note that, the terms of the sequence are positive.