Cauchy sequences. 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:
 
 A: 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})| $$
A: 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.
