Prove that sequence $a_{n+1} = \frac{1}{1+a_n}$ is bounded?

Consider sequence;
$$a_1 = 1$$
$$a_{n+1} = \frac{1}{1+a_n}$$
Prove that sequence is bounded.

It is a question from my test. I couldn't figure out how to solve it.

• Hint : $a_n$ is always positive, so... – Alain Remillard Nov 24 '15 at 15:04
• You're iterating the function $f(x)=\frac{1}{x+1}$. Since $|f'(x)|<1$ on $(0,\infty)$ and the function maps this interval into itself, an iteration started in this interval will always converge towards its fixpoint. – Henning Makholm Nov 24 '15 at 15:05
• Show that $a_n = \frac{F_n}{F_{n+1}}$ using the recurrence formula of the Fibonacci numbers. – gammatester Nov 24 '15 at 15:10
• @gammatester Isn't it a bit overkill? All the OP is asking is to prove that the sequence is bounded. – Clement C. Nov 24 '15 at 15:11
• @Clement C: Admitted, but if you look at the first terms it is obvious and you get the limit as a bonus. – gammatester Nov 24 '15 at 15:13

First of all, you have to "feel" how does this sequence evolve. Computing the first terms, we have: $$1, 0.5, 0.66666666, 0.6, 0.625, 0.615, 0.619, ....$$

We see that this sequence go up and down in a decreasing interval and that the values are all in $[0.5, 1]$.

We have a feeling about what's happening. So now, you only have to prove (by recurrence) that for all $n\in \mathbb N$, $\frac{1}{2} \le a_n \le 1$. Do you follow that?

$$a_n > 0$$ $$a_{n+2}=\frac{1}{1+a_{n+1}}=\frac{1}{1+\frac{1}{1+a_n}}=\frac{1+a_n}{2+a_n}=1-\frac{1}{2+a_n}$$ $$\therefore \frac{1}{2}\leq a_{n}\leq 1\quad$$

• No, $a_2=\frac{1}{2}$. So make it $1/2\leq a_n\leq 1$ and you've got a correct answer. Why the aversion or $\leq$, forcing you to write the special case $n>2$? – Thomas Andrews Nov 24 '15 at 15:28
• Also $a_1=1$ and $a_2=1/2$, to start the induction. – egreg Nov 24 '15 at 16:01

If $a_n$ is positive then

$$a_{n+1} = \frac{1}{1 + a_n} > 0.$$

Also, if $a_n$ is positive, then $$1 < 1 + a_n \implies 1 > \frac{1}{1 + a_n} \implies 1 > a_{n+1}.$$ Therefore, if $a_{n} > 0$ then $$0 < a_{n + 1} < 1.$$ That is, if all the elements of the sequence are positive then the sequence is bounded. Since the first element is positive ($a_1 = 1$), the first equation proves by induction that all the elements will be positive.