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.

  • 7
    $\begingroup$ Hint : $a_n$ is always positive, so... $\endgroup$ – Alain Remillard Nov 24 '15 at 15:04
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 24 '15 at 15:05
  • 2
    $\begingroup$ Show that $a_n = \frac{F_n}{F_{n+1}}$ using the recurrence formula of the Fibonacci numbers. $\endgroup$ – gammatester Nov 24 '15 at 15:10
  • 1
    $\begingroup$ @gammatester Isn't it a bit overkill? All the OP is asking is to prove that the sequence is bounded. $\endgroup$ – Clement C. Nov 24 '15 at 15:11
  • $\begingroup$ @Clement C: Admitted, but if you look at the first terms it is obvious and you get the limit as a bonus. $\endgroup$ – 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$$

  • $\begingroup$ 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$? $\endgroup$ – Thomas Andrews Nov 24 '15 at 15:28
  • $\begingroup$ Also $a_1=1$ and $a_2=1/2$, to start the induction. $\endgroup$ – 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.


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.