# why is this sequence convergent

Suppose to have two sequence $(a_n)_{n\geq1}$ and $(b_n)_{n\geq1}$ such that

$a_n=\frac{1}{2}(a_{n-1}+b_{n-1})$.

I want to prove that if $b_n\rightarrow0$ then $a_n\rightarrow0$.

The only thing I was able to prove is that $a_n$ is bounded, in fact:

$b_n$ is convergent and so bounded $|b_n|\leq M$. And so $|a_n|\leq |\frac{a_2}{2^{n-1}}+\frac{b_2}{2^{n-2}}+\cdots+\frac{b_{n-1}}{2}|\leq|\frac{a_2}{2^{n-2}}|+M\sum^\infty_{k=1}\frac{1}{2^k}$ and for great $n$ we have $|\frac{a_2}{2^{n-2}}|\leq\varepsilon$

Could you help me to continue (if I'm on the right track), please?

I see that if we prove that $a_n$ has a limit $L$ then necessarily $L=0$ because $L$ must satisfy $L=\frac{1}{2}L$, but I don't know how to prove that it has a limit.

-
+1 for showing your work –  Jyrki Lahtonen Oct 10 '11 at 6:00
Hint: If $n$ is large, the early terms of your middle expression are small (not just the $a_2$ one) because of the large power of 2, and the later terms are small because $b_n$ tends to zero. So can you see how to split the sequence differently, and get a better estimate? –  Mark Bennet Oct 10 '11 at 6:06
@Mark Sorry 'bout ruining your hint with my answer. I didn't see your comment soon enough :-( –  Jyrki Lahtonen Oct 10 '11 at 6:14
@JyrkiLahtonen: no hard feelings ... The technique of splitting a problem into pieces which are dealt with in different ways seemed worth noting anyway. In measure theory, for example, there are a number of proofs which require a proof for "most" points of a set based on some kind of regularity, and a proof for the remaining "problem" points by showing that they are confined to a set of arbitrarily small measure. –  Mark Bennet Oct 10 '11 at 7:09

Hint: You have a good start in proving that the sequence $(a_n)$ is bounded. Let's reuse your trick and look at $$a_{2n}=\frac{a_n}{2^n}+\frac{b_{2n-1}}2+\frac{b_{2n-2}}4+\cdots+\frac{b_n}{2^n}.$$ All the numbers $|b_k|<\epsilon$ for $k\ge n$, if $n$ is large enough. The first term $a_n/2^n$ looks like it would be under control as well now that you know $|a_n|$ to be bounded.

-

Assume that $-t\leqslant b_n\leqslant t$ for a given positive $t$ and for every $n\geqslant n_t$. Then $a_n-t\leqslant\frac12(a_{n-1}-t)$ and $a_n+t\geqslant\frac12(a_{n-1}+t)$ for every $n\geqslant n_t$. Thus $\limsup (a_n-t)\leqslant0$ and $\liminf (a_n+t)\geqslant0$. Since this holds for every positive $t$, $a_n\to 0$.

-
@Srivatsan, exactly. Thanks. –  Did Oct 10 '11 at 17:29

One way to do this is to view the recursion equation defining $a_n$ as a, well, recursion equation. It is then a non-homogeneous linear recursion, whose associated homogeneous recursion is very easy to solve. One could then use Lagrange's method of variation of parameters to determine the actual solution, but instead of doing that (we can't, in fact, because we do not know $b_n$) we can use the same idea to obtain bounds that will prove what you want. Let's do that.

Let $\varepsilon>0$. There exists an $N$ such $|b_n|\leq\varepsilon$ for all $n\geq N$.

Let $a_n=\frac{\alpha_n}{2^n}$ (this is where we use Lagrange's method: the solution for the homogeneous equation is $\frac{\alpha}{2^n}$, with $\alpha$ a constant and Lagrange suggests that we now turn $\alpha$ into a function $\alpha_n$ of $n$) and suppose that $|b_n|\leq\beta$ for all $n\geq1$. Replacing this in the defining recursion tells us that $$|\alpha_n-\alpha_{n-1}|=2^{n-1}|b_n|$$ for all $n\geq1$. This implies that when $n\geq N$ \begin{align}|\alpha_n-\alpha_0|&\leq|\alpha_n-\alpha_{n-1}|+|\alpha_{n-1}-\alpha_{n-2}|+\cdots+|\alpha_1-\alpha_0| \\ &\leq(2^{n-1}+\cdots+2^N)\varepsilon + (2^{N-1}+\cdots+2^0)\beta\\&\leq (2^n-2^N)\varepsilon+(2^N-1)\beta \\&\leq 2^n \varepsilon+c\end{align} for some positive constant $c$. Then $$|\alpha_n|\leq 2^n\varepsilon+c+|\alpha_0|$$ and $$|a_n|=|\alpha_n/2^n|\leq\varepsilon+\frac{c+|\alpha_0|}{2^n}.$$ This should make it clear that $a_n\to0$.

-
One can probably enhance this to a statement telling us that solutions to a non-homogeneous perturbation which gets smaller and smaller of a linear homogeneous recursion with all characteristic roots in $(-1,1)$ is not very different from the unperturbed solutions. –  Mariano Suárez-Alvarez Oct 10 '11 at 6:28