How to create a formula for a recursive sequence?

Question

Let $\left (a_n \right )_{n=1}^{\infty}$ be an infinite sequence.

$\left (a_n \right )_{n=1}^{\infty}$ is defined by:

$a_1 = 0$ $\; \; \; a_{n+1} = \frac{1}{1+ a_n}\; \; \forall n \in \mathbb{N}$

I need to show that $\left (a_n \right )_{n=1}^{\infty}$ converges and find it's limit. I want to do it by finding a formula for both $a_{2k}$ and $a_{2k-1}$ and then use some basic limit arithmetics rules, however I didn't manage to find a formula for both sub-sequences.

I would love to get some recommendations on how to find such formula and how to approach these kind of questions.

Thanks!

Answer 1

If you try to compute some initial terms, then you can find that $$ 0, 1, \frac{1}{2}, \frac{2}{3}, \frac{3}{5}, \frac{5}{8}, \frac{8}{13}, \dots $$ which seems to be a sequence with famous numbers in it. In fact, as one expect, these are Fibonacci numbers and we have $$ a_{n} = \frac{F_{n-1}}{F_{n}}, $$ where $F_{n}$ is $n$-th Fibonacci number given by $F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1} + F_{n-2}$. We can prove this by using mathematical induction. There exists a general formula of Fibonacci number (which can be derived by using characteristic polynomials) $$ F_{n} = \frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^{n} - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^{n} = \frac{1}{\sqrt{5}} (\phi^{n} - \bar{\phi}^{n}). $$ Hence this gives a general formula for $a_{n}$: $$ a_{n} = \frac{\phi^{n-1} - \bar{\phi}^{n-1}}{\phi^{n} - \bar{\phi}^{n}} $$ for $\phi = \frac{1 + \sqrt{5}}{2}, \bar{\phi} = \frac{1-\sqrt{5}}{2}$.

Answer 2

If the sequence has a limit $a$, then it satisfies $a = \frac{1}{1+a}$, which tells you what the limit is.

But your idea is the right way to show that the limit exists. If you take every other term starting from $0$ you get $0, \frac{1}{2}, \frac{3}{5}, \frac{8}{13}, \frac{21}{34}, \dots$ which may be familiar.

If you take every other term starting from $1$ you get $1, \frac{2}{3}, \frac{5}{8}, \frac{13}{21}, \dots$ which is even more eerily familiar. (Look at the numerators and denominators of the two sequences.)

Now just show that the first sequence is increasing and the second is decreasing, and that their ratio is tending to $1$.

Answer 3

If the limit where to exist, then $L=\lim_{a_n}=\lim{a_{n+1}}$, then $a_{n+1} = \frac{1}{1+ a_n}$ implies $L = \frac{1}{1+ L}$ by taking limits.

Which gives, $L^2+L-1=0$, solving this equation gives $L=\frac{-1\pm\sqrt{5}}{2}$. Since $L>=0$, $L=\frac{-1+\sqrt{5}}{2}$

Now, how do you know the limit exists? You have to find a lower bound and show it's decreasing, this would prove it converges. Do you see how?(Obviously 0 is a lower bound)