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.
 A: 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.
A: 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$.
A: 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.
A: 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.
