# Prove that the sequence given by $c_n = \sqrt{1+c_{n-1}}$ converges and find the limit

Let $c_1 = 2$, and for $n > 1$, let $c_n = \sqrt{1+c_{n-1}}$. Prove:

1. (by induction) that $c_n < 2$, for $n > 1$.

2. (by induction) that {$c_n$} is monotonically decreasing.

3. that the sequence {$c_n$} converges.

4. What does the sequence converge to?

I'm not sure how to approach this problem, let alone how to do it. Any help would be much appreciated.

• if $c_k<2$ observe that $1+c_k<3<4$ and so $c_{k+1}=\sqrt{1+c_k}<2$; now show $c_n<2$ for $n=2$. – oldrinb Sep 4 '13 at 5:01
• "I'm not sure how to approach this problem"... Problably by just following the spelled out steps? If you are given a problem with a very detailed description on what to do, you should sit down and follow the description instead of asking in internet boards. You learn nothing this way! – Kofi Sep 4 '13 at 6:16

Step 1: We prove by induction that $c_{n+1}\lt c_n$ for all $n$.

By a direct calculation we can check that $c_2\lt c_1$.

Suppose that for a particular $k$, we have $c_{k+1}\lt c_k$. We will show that $c_{k+2}\lt c_{k+1}$.

We have $c_{k+2}=\sqrt{1+c_{k+1}}$. But by the induction assumption, $c_{k+1}\lt c_k$, and therefore $\sqrt{1+c_{k+1}}\lt \sqrt{1+c_k}$. It follows that $$c_{k+2}=\sqrt{1+c_{k+1}}\lt \sqrt{1+c_k}=c_{k+1}.$$ This completes the induction step.

Step 2: Our sequence is obviously bounded below, for example by $0$. Since the sequence is monotonically decreasing, and bounded below, it has a limit $a$.

Step 3: We have $$a=\lim_{n\to\infty}c_{n+1}=\lim_{n\to\infty}\sqrt{1+c_n}=\sqrt{1+a}.$$ If we need justification for the last step, it is by the continuity of the function $\sqrt{1+x}$.

It follows that $a=\sqrt{1+a}$. Any root of this equation is a root of $a^2-a-1=0$.

The positive root $a^2-a-1=0$ is $\dfrac{1+\sqrt{5}}{2}$. That is our limit.

The Golden Ratio strikes again!

To prove it is bounded above by $2$ observe we can assume for some $k$ that $c_k<2$ and it follows $1+c_k<3<4$ and so $c_{k+1}=\sqrt{1+c_k}<2$. Show $c_2<1$ holds and by the principle of induction we have that it holds for $n>1$.

To prove it's decreasing try something like $c_k<c_{k-1}$ hence $1+c_k<1+c_{k-1}$ and $c_{k+1}=\sqrt{1+c_k}<\sqrt{1+c_{k-1}}=c_k$. Now show $c_3<c_2$ and by the principle of induction it holds for $n>1$.

We can use the monotone convergence theorem to conclude $\{c_n\}$ converges. To determine the limit itself, assume $\lim\limits_{n\to\infty}c_n=L$. Now observe:\begin{align*}\lim_{n\to\infty}c_n&=\lim_{n\to\infty}\sqrt{1+c_{n-1}}\\L&=\sqrt{1+L}\\L^2-L-1&=0\end{align*}This gives us only one positive real root, $L=\varphi=\frac12(1+\sqrt5)$ i.e. the golden ratio.