2
$\begingroup$

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.

Be glad for help.

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

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.

$\endgroup$
  • $\begingroup$ Great. Thank you too! $\endgroup$ – AndrePoole Mar 27 '14 at 17:41
  • $\begingroup$ But what does it converge to?! (Pretty sure it's $5/3$.) $\endgroup$ – Paul Z Mar 27 '14 at 18:10
  • $\begingroup$ 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. $\endgroup$ – user138335 Mar 27 '14 at 18:17
  • 2
    $\begingroup$ How did you know $|a_n-a_{n-1}|=\frac{1}{2^{n-2}}$ ? $\endgroup$ – GinKin Mar 30 '14 at 13:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note: I changed a mistake in the beginning. $\endgroup$ – Marc Mar 27 '14 at 17:37
  • $\begingroup$ Cool. So easy after reading the solution :p $\endgroup$ – AndrePoole Mar 27 '14 at 17:39
  • $\begingroup$ Can you please explain how to show that it's Cauchy ? $\endgroup$ – GinKin Mar 30 '14 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Marc Mar 30 '14 at 15:04
  • $\begingroup$ 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. $\endgroup$ – GinKin Apr 2 '14 at 14:45

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.