2

Well my question is how to prove this:

Let $a_{0}$, $a_{1}$ be distinct real numbers.Define:

$$a_{n}=\frac{a_{n-1}+a_{n-2}}{2}$$ for each positive integer $n\ge2$.Show that $\{a_{n}\}$ is a Cauchy sequence. (Hint: You may want to use induction to show that: $a_{n+1}-a_{n}=(\frac{-1}{2})^{n}(a_{1}-a_{0})$, and then use the result of $\sum x^{n}=\frac{1-x^{n+1}}{1-x}$). And can you help me with the induction please because it does not give me the correct result. thank you.

My induction, for $n=0$ is obvious, now for $n=1$, we have: enter image description here

user162343
  • 3,245
  • Can you show what you have tried for proving $a_{n+1}- a_n = \left(-\frac{1}{2}\right)^n \left(a_1 - a_0\right)$ by induction? – Joshua Mundinger Sep 06 '14 at 14:54
  • Yes @Alqatrkapa I write it in the question. :) – user162343 Sep 06 '14 at 14:55
  • Hint: To simplify a bit define $y_{n} = a_n - a_{n-1}$ then the equation reads $y_{n} = \left(-\frac{1}{2}\right) y_{n-1}$ and you must show that $y_{n+1} = \left(-\frac{1}{2}\right)^n y_1$ – Winther Sep 06 '14 at 14:58

2 Answers2

1

Hints

When you have a recurrence relation of this form, the trick is to let your inductive statement $ p(n) $ cover two levels. With reference to this question define your inductive statement thus,

$$ P(n): \; \text{$a_{n+ 1} - a_n = \left({\dfrac{-1}{2}}\right)^n(a_1 - a_0) \;$ AND $ \; a_{n+ 2} - a_{n+1} = \left({\dfrac{-1}{2}}\right)^{n+1}(a_1 - a_0) $} $$

You have to do one additional piece of calculation for the base case but you will find the inductive step is made considerably easier.

Now you will note that when $m \gt n$,

$$ |a_m - a_n| = |(a_m - a_{m-1}) + (a_{m-1} - a_{m-2}) + ... + (a_{n+1} - a_{n})| \le |a_m - a_{m-1}| + ... + |(a_{n+1} - a_{n})| $$

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
1

I'll start proving by induction that $a_{n+1}-a_{n}=(\frac{1}{2})^{n}(a_{1}-a_{0})$. You did the case $n=1$, so that's done. For the inductive step, we look at:

$$ a_{n+2}-a_{n+1} $$

assuming that $a_{n+1}-a_{n}=(\frac{1}{2})^{n}(a_{1}-a_{0})$ is true for $n$ (induction hypothesis). Then,

$$ a_{n+2}-a_{n+1} = \frac{a_{n+1}+a_{n}}{2} - a_{n+1} = -\frac{a_{n+1}-a_{n}}{2} = -\frac{1}{2}(\frac{-1}{2})^{n}(a_{1}-a_{0}) = (\frac{-1}{2})^{n+1}(a_{1}-a_{0}). $$

Now, that identity is proven. We're left to see that the sequence is Cauchy. Thus, we must show that $\forall \epsilon > 0$, $\exists N\in \mathbb{N}$ such that $n,m>N \implies$ $$ |a_{m}-a_{n}|\lt \epsilon $$

Fix some $\epsilon > 0$. We can obvioulsy assume $m \gt n$. Then, $m=n+k$ for some positive $k$. Then, we look at

$$ |a_{m}-a_{n}| = |a_{n+k}-a_{n}| = |a_{n+k}-a_{n+k-1}+a_{n+k-1} - \ldots -a_{n+1}+a_{n+1}-a_{n}| \\ \leq |a_{n+k}-a_{n+k-1}| + \ldots + |a_{n+1}-a_{n}| \\ = (|\frac{-1}{2}|^{n+k-1} + \ldots + |\frac{-1}{2}|^{n+1} + |\frac{-1}{2}|^{n})|a_{1}-a_{0}| \\ =\frac{1}{2^{n}}(\frac{1-(\frac{1}{2})^{k}}{\frac{1}{2}})|a_{1}-a_{0}|\\ =\frac{1}{2^{n-1}}(1-\frac{1}{2^{k}})|a_{1}-a_{0}| \\ \leq \frac{|a_{1}-a_{0}|}{2^{n-1}} $$

Then, you pick an $N>0$ such that $\frac{|a_{1}-a_{0}|}{2^{N-1}} < \epsilon$, given that that quantity gets as small as you want, and decreases monotonically.

Vinícius Novelli
  • 2,487