# A recursive sequence is defined by…

A sequence is defined recursively by $a_1=1$ and $a_{n+1} = 1 + \frac{1}{1+a_{n}}$.

Find the first eight terms of the sequence $a_n$. What do you notice about the odd terms and the even terms? By considering the odd and even terms separately, show that $a_n$ is convergent and deduce that its limit is $\sqrt{2}$.

EDIT: Ok, so I was being an idiot and forgot how to basic math for a little. The first 8 terms are as follows:

EVENS:

a2 = 1.5
a4 = 1.46666...
a6 = 1.415731...
a8 = 1.41426...


ODDS:

a1 = 1
a3 = 1.4
a5 = 1.4054...
a7 = 1.41395...


From these I see that the even terms are decreasing while the odd terms are increasing. How can I use these to prove that $\{a_n\}$ converges? Does it have something to do with alternating series or something similar?

• Have you tried to do this question on your own? Did you find the first $8$ terms? Did you notice anything? Any other thoughts of your own on the question? – Omnomnomnom May 29 '15 at 22:55
• I found the first 8 terms yes, ( obviously the easy part). The only thing I noticed was that on the even terms there was an odd numerator with an even denominator and the opposite was true for the odd terms. Both even and odd terms keep becoming closer to 1. – Zearia May 29 '15 at 23:11
• I must be missing something obvious, looking at the decimal or fraction values of the even and odd terms I just don't see anything that I could use to prove convergence. I see even less information from decimal values. – Zearia May 29 '15 at 23:17
• You've had exactly the right insight! The even terms form a decreasing sequence while the odd terms are increasing. It suffices now to separately prove that the sequence of evens converges to $\sqrt 2$ and that the sequence of odds converges to $\sqrt 2$ – Omnomnomnom May 29 '15 at 23:32
• @mvw I think your answer should stay – Omnomnomnom May 29 '15 at 23:42

## 3 Answers

We have $a_{n+1} = 1 + \frac{1}{1+a_{n}} = \frac{2+a_n}{1+a_{n}}$. Therefore, $a_n > 1$ for all $n$.

Also,

$\begin{array}\\ a_{n+1}-\sqrt{2} &= \dfrac{2+a_n}{1+a_{n}}-\sqrt{2}\\ &= \dfrac{2+a_n-\sqrt{2}(1+a_n)}{1+a_{n}}\\ &= \dfrac{2-\sqrt{2}-a_n(\sqrt{2}-1)}{1+a_{n}}\\ &= \dfrac{(\sqrt{2}-1)(\sqrt{2}-a_n)}{1+a_{n}}\\ \end{array}$

so $\dfrac{a_{n+1}-\sqrt{2}}{\sqrt{2}-a_n} =\dfrac{\sqrt{2}-1}{1+a_{n}}$.

Therefore (1)$a_n-\sqrt{2}$ alternates in sign and (2)$\big|\dfrac{a_{n+1}-\sqrt{2}}{\sqrt{2}-a_n}\big| <\sqrt{2}-1$. This implies that $a_n-\sqrt{2} \to 0$ so that $\lim_{n \to \infty} a_n =\sqrt{2}$.

Hint: $\sqrt{2}$ is a piece of cheese, $a_{2n}$ is a slice of bread, $a_{2n+1}$ is another slice of bread. What would you do next?

• For those who dislike sandwich metaphors: $a_{2n} \geq \sqrt 2 \geq a_{2n + 1}$ – Omnomnomnom May 29 '15 at 23:36
• Also, if we add slices of bread for each $n$, the cheese to bread ratio would be completely unappetizing – Omnomnomnom May 29 '15 at 23:37
• Guess what I am eating right now. :-) – mvw May 29 '15 at 23:39
• And this "answer" is moldy. – marty cohen May 31 '15 at 3:16

Hint: Applying the recurrence relation twice, we find that $$a_{n+2} = 1 + \frac{1}{1+a_{n+1}} = 1 + \frac{1}{1+\left(1 + \frac{1}{1+a_{n}}\right)} = \\ 1 + \frac{1}{2 + \frac{1}{1+a_{n}}}=\\ 1 + \frac{1+a_n}{2 + 2a_n + 1} =\\ 1 + \frac{1+a_n}{3 + 2a_n} = \\ \frac{3 + 2a_n + 1+a_n}{3 + 2a_n} = \\ \frac{4 + 3a_n}{3 + 2a_n}$$ This recurrence gives us both the even and odd sequences. We need to show one of the following:

• The evens decrease to $\sqrt 2$ and the odds increase to $\sqrt 2$
• The evens stay above $\sqrt 2$, the odds stay below $\sqrt 2$, and the difference between the evens and odds converges to $0$.
• Sorry this is so delayed, I had to step away for a while. So is (4+3an)/(3+2an) both the even and odd sequences? Do you mean that it is both the sequences combined? I follow how you arrived at that point, but I don't understand what it means in relation to the problem. – Zearia May 30 '15 at 4:23