3
$\begingroup$

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.

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

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You have only shown that the limit is $(1+\sqrt{5})/2$ provided it exists. $\endgroup$ – egreg May 18 '13 at 12:57
  • $\begingroup$ That is true... $\endgroup$ – Eddy May 18 '13 at 13:04
  • $\begingroup$ Amire Bendjeddou's technique is very good for solving the problem. $\endgroup$ – egreg May 18 '13 at 13:10
  • $\begingroup$ Is there any theorem that states that a bounded sequence which increases for even and decreases for odd is convergent. $\endgroup$ – Eddy May 18 '13 at 13:13
  • $\begingroup$ @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. $\endgroup$ – Stefan Smith May 18 '13 at 15:39
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.