<s>[INST] 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.
 [/INST] 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$.
</s>