# Show that a recursive sequence converges

Let $a_1 = 1, a_2 = 2$ and $a_n = {1\over 2}(a_{n-1}+a_{n-2})$
Show that the sequence converges.

At first I thought using the theorem which says that a bounded and monotone sequence converges, but the sequence (at least the first terms) is not monotone.

I suspect I should use Cauchy's criteria but don't know how to apply it here.

• en.wikipedia.org/wiki/Recurrence_relation#Solving – T_O Mar 27 '14 at 17:33
• I am familiar with these methods, yet that's not the approach I am expected to use here. – AndrePoole Mar 27 '14 at 17:35
• Ok I didn't know that. Marc's method probably works better anyway ;) – T_O Mar 27 '14 at 17:36

We can prove that $$|a_n-a_{n-1}|=\frac{1}{2^{n-2}}$$

You can check that it works for $n=2$. Assuming it holds for $n$, we have $$|a_{n+1}-a_n|=\left|\frac{a_n+a_{n-1}}{2}-a_n\right|={1\over 2}|a_{n-1}-a_n|={1\over 2}|a_n-a_{n-1}|={1\over 2}\frac{1}{2^{n-2}}=\frac{1}{2^{n+1-2}}$$

This should lead to a proof of convergence.

• Great. Thank you too! – AndrePoole Mar 27 '14 at 17:41
• But what does it converge to?! (Pretty sure it's $5/3$.) – Paul Z Mar 27 '14 at 18:10
• Yes it's 5/3. I got that using Generating functions (my formula was $a_n=1+2/3(1+(-1)^{n+1}/2^n)$) but I didn't think that was relevant to the question. – user138335 Mar 27 '14 at 18:17
• How did you know $|a_n-a_{n-1}|=\frac{1}{2^{n-2}}$ ? – GinKin Mar 30 '14 at 13:03

Hint: Use the fact that $$|a_{n}-a_{n-1}| = |\frac{1}{2}(a_{n-1} + a_{n-2}) - \frac{1}{2}(a_{n-2} + a_{n-3})| = |\frac{1}{2}a_{n-1} - \frac{1}{2}a_{n-3}| = |\frac{1}{2}\frac{1}{2}(a_{n-2} + a_{n-3}) - \frac{1}{2}a_{n-3}| = \frac{1}{4}|a_{n-2}-a_{n-3}|$$ From here on it is easier to show that the sequence is Cauchy.

• Note: I changed a mistake in the beginning. – Marc Mar 27 '14 at 17:37
• Cool. So easy after reading the solution :p – AndrePoole Mar 27 '14 at 17:39
• Can you please explain how to show that it's Cauchy ? – GinKin Mar 30 '14 at 13:06
• By adapting my proof a little bit we can see that $|a_{n+1}-a_n| = \frac{1}{2}|a_n-a_{n-1}|$. This means, since $|a_2 - a_1| = 1$, that $|a_{n+1}-a_n| = \frac{1}{2}|a_n-a_{n-1}| = \frac{1}{4}|a_{n-1}-a_{n-2}| = \ldots = \frac{1}{2^{n-1}}|a_2-a_1| = \frac{1}{2^{n-1}}$. Let $\epsilon>0$. Now choose $N$ such that $\frac{1}{2^{N-1}} < \epsilon$. Then $|a_{n+1}-a_n| \le|a_{N+1}-a_N| < \epsilon$ for all $n\ge N$. Thus the sequence is Cauchy. – Marc Mar 30 '14 at 15:04
• Thanks, didn't notice you answered. But shouldn't a Cauchy sequence meet Cauchy criterion for every $n,m$ in $|a_n-a_m|<\epsilon$ ? not just two adjacent elements. – GinKin Apr 2 '14 at 14:45