Proving convergence of sequence with induction

Question

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.

Answer 1

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

Answer 2

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

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

Answer 4

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.