# Proving convergence of sequence with induction

I have a sequence defined as $a_{1}=\sqrt{a}$ and $a_{n}=\sqrt{1+a_{n-1}}$ and I need to prove that it has an upper bound and therefore is convergent. So i have assumed that the sequence has a limit and by squaring I got that the limit is $\frac{1+\sqrt{5}}{2}$ only $\mathbf{if}$ it converges.

What methods are there for proving convergence? I am trying to show that $a_{n}<\frac{1+\sqrt{5}}{2}$ by induction but could use some help since I have never done induction proof before.

Progress:

Step 1(Basis): Check if it holds for lowest possible integer: Since $a_{0}$ is not defined, lowest possible value is $2$.

$a_{2}=\sqrt{1+a_{1}}=\sqrt{1+\sqrt{a}}=\sqrt{1+\sqrt{\frac{1+\sqrt{5}}{2}}}< \frac{1+\sqrt{5}}{2}$.

Step 2: Assume it holds for $k\in \mathbb{N},k\geq 3$. If we can prove that it holds for $n=k+1$ we are done and therefore it holds for all $k$.

This is were i am stuck: $a_{k+1}=\sqrt{1+a_{k}}$. I don't know how to proceed because I don't know where I am supposed to end.

-
What is $a$?${}{}{}$ – P.. Jan 15 '13 at 6:01

Hint: Use the Monotone Convergence Theorem: MCT. That is, show that $a_n$ is monotone increasing, and bounded above. Increasing should be evident...

Find any upper bound: $\,3\,$ maybe?; there's no need to find the least upper bound if you only need to prove convergence.

If you can do that, then by the Monotone Convergence Theorem, you can conclude the sequence converges.

Then you are done, if you only need to prove convergence.

THEN, if you want to find the value to which the sequence converges, assume $L=\lim_{n\to\infty}a_n$. Then $L$ must satisfy $L=\sqrt{1+L}$, and solve for $L$.

-
+1 for the nice insights, yet...The sequence is monotone increasing from some definite index n and on, depending heavily on what $\,a>0\,$ is. Before that index, the sequence is decreasing, and there can be lots of indexes with that characteristic. In fact, I think it is possible to prove for any $\,k\in\Bbb N\,$ there exists $\,a(k)=a>0\,$ big enough so that $\,\{a_n\}_{n\leq k}\,$ is decreasing. – DonAntonio Jan 15 '13 at 3:17

So the problem is to show that is bounded above by $\dfrac{1+\sqrt{5}}{2}$.

Why don't you prove something easier, that is bounded above by $3$?

-

Hint: Show that it is monotone and bounded. This guarantees convergence; then suppose $L=\lim_{n\to\infty}a_n$. Then $L$ must satisfy $$L=\sqrt{1+L}.$$ Solve for $L$.

-
There's an induction problem on sequences here math.stackexchange.com/questions/510591/… if u guys are interested. – user87274 Oct 1 '13 at 13:52
@mespebjidom: It seems you already have a fine answer posted. – Clayton Oct 1 '13 at 13:56

Let $f(x) = \sqrt{1+x}-x$. We find that $f'(x) = \frac 1 {2\sqrt{1+x}} -1 <0$. This means that $f$ is a strictly decreasing function. Set $\phi = \frac{1+\sqrt 5}{2}$.

We now that $f(\phi)=0$. We must then have that $f(x)>0$ if $x<\phi$ and $f(x)<0$ if $x>\phi$. So $a_{n+1}>a_n$ if $a_n< \phi$ and $a_{n+1} < a_n$ if $a_n > \phi$.

I claim that if $a_1<\phi$ then $a_n < \phi$ for all $n$. This is proven by induction. Assume that $a_k < \phi$. Then $a_{k+1}^2 = a_k +1 < 1+\frac{1+\sqrt 5}{2}= \frac{6+2\sqrt{5}}{4} =\phi^2$. So $a_{k+1} < \phi$ and by induction we get that $a_n < \phi$ for all $n$.

If $a_1<\phi$ we thus know that we get a bounded increasing sequence. All bounded increasing sequences converge. To deal with the case when $\sqrt {a_1}>\phi$ is left as an exercise.

-