# Limit of a sequence

Let $\{u_n\}$ be a sequence of nonnegative numbers satisfying the condition $$\tag{1} u_{n+1}\leq (1-\alpha_n)u_n+\beta_n \quad \forall n\in\mathbb{N},$$ where $\{\alpha_n\}$ and $\{\beta_n\}$ are sequences of real numbers such that

$\tag{2}\displaystyle\lim_{n\rightarrow\infty}\alpha_n=0$

$\tag{3}\displaystyle\sum_{n=0}^{\infty}\alpha_n=\infty$

$\tag{4} \displaystyle\sum_{n=0}^{\infty}\beta_n<\infty$

Prove that $$\displaystyle\lim_{n\rightarrow\infty}u_n=0$$

-
Hint: Try to prove the contrapositive. "If u_n does not tend to 0, then there exists an epsilon and n_0 such that |u_n| >= epsilon for all n >= n_0..." – Adam Rubinson May 3 '12 at 0:53
@AdamRubinson, that's not the contrapositive exactly, since "If u_n doesn't tend to 0" means what you wrote or that there is no limit at all, which would allow for the series to visit as close to 0 as you like infinitely often. – davin May 3 '12 at 9:28
Actually davin, you are right. I guess what I meant to say was: "there exists an epsilon such that for every n_o, there is an n_1 > n_0 such that |u_(n_1)| > epsilon". But the main point is that, assuming the result in the OP is true, it should be provable using epsilon's and delta's (if OP is familiar with these), probably along with AOL. – Adam Rubinson May 3 '12 at 12:28
drmath: Any luck with my answer below? – Did May 7 '12 at 12:07

Nota: The hypothesis that $\alpha_n\geqslant0$ for every $n$ is obviously missing from the question, and the solution below assumes it.

Preliminary step: Show that one can assume without loss of generality that $\alpha_n\lt1$ for every $n$. From now on, we assume this.

First step: Show by a recursion over $n\geqslant0$ that $u_n\leqslant A_{n-1}u_0+A_{n-1}\sum\limits_{k=0}^{n-1}A_k^{-1}\beta_k$ where $A_{-1}=1$ and, for every $k\geqslant0$, $A_k=\prod\limits_{i=0}^k(1-\alpha_i)$.

Second step: Show that $A_n\to0$ when $n\to\infty$. Hint: $\log A_n\leqslant-\sum\limits_{k=0}^n\alpha_k$.

Third step: Show that, for every $n\geqslant k\geqslant 0$, $u_n\leqslant A_{n-1}u_0+A_{n-1}\sum\limits_{i=0}^{k-1}A_i^{-1}\beta_i+\sum\limits_{i\geqslant k}\beta_i$.

Fourth step: conclude.

For every $\varepsilon\gt0$, there exists $K_\varepsilon$ such that $\sum\limits_{i\geqslant K_\varepsilon}\beta_i\leqslant\varepsilon$. Then, there exists $M_\varepsilon$ such that $A_{M_\varepsilon-1}\sum\limits_{i=0}^{K_\varepsilon-1}A_i^{-1}\beta_i\leqslant\varepsilon$. Let us choose $N_\varepsilon\geqslant M_\varepsilon$ such that $A_{N_\varepsilon-1}u_0\leqslant\varepsilon$. Then $u_n\leqslant3\varepsilon$ for every $n\geqslant N_\varepsilon$.

-
In your first step, did you intend $\leqslant$ instead of $=$? – robjohn May 3 '12 at 23:03
In your third step, you seem to be assuming that $\alpha_i>0$ (so that $A_i$ is monotonic). Is that so? – robjohn May 3 '12 at 23:06
@robjohn: Thanks for your remarks. First step: you are right, one should read $\leqslant$. Third step: why should one assume this? One needs that $(A_n)_n$ is nonincreasing hence some $\alpha_n$s may be zero. Exercise: reduce the general case to the case when $\alpha_n\gt0$ for every $n$, changing the sequence $(\beta_n)_n$. – Did May 4 '12 at 5:51
I'm sorry, I meant that you were assuming that $\alpha_n$ was non-negative. That was not specified, and I believe it should be because otherwise, there is a counterexample. It also appears that your proof assumes $\beta_n$ is non-negative. This, also, is not specified, and is not necessary, as long as $\sum|\beta_n|<\infty$. – robjohn May 4 '12 at 6:44
@Didier Is it legitimate to think that since $\sum \alpha_n$ diverges but $\alpha_n \ to 0$, then it should be the case $\{ \alpha_n \}$ should have arbitrarily long strings of elements such that their sign is the same? I was trying to tackle the problem from this point of view but I really didn't succeed. – Pedro Tamaroff May 9 '12 at 0:42

There must be some missing constraints. If $\alpha_n$ is allowed to be negative, we get the following counterexample. $\smash{\rlap{\phantom{\Bigg(}}}$

Define $$u_{n+1}=(1-\alpha_n)u_n+\beta_n\tag{1}$$ and $$A_n=\prod_{k=1}^{n-1}(1-\alpha_k)\tag{2}$$ By induction, it can be verified that $$u_n=A_n\left(u_1+\sum_{k=1}^{n-1}\frac{\beta_k}{A_{k+1}}\right)\tag{3}$$ For $j\ge1$, define $$n_j=\left\{\begin{array}{} 2^{j(j-1)/2}&\text{when }j\text{ is odd}\\ 2^{j(j-1)/2+1}&\text{when }j\text{ is even} \end{array}\right.\tag{4}$$ and for $n\ge1$, $$\alpha_n=\left\{\begin{array}{} \frac{1}{n+1}&\text{for }n_j\le n< n_{j+1}\text{ when }j\text{ is odd}\\ -\frac1n&\text{for }n_j\le n< n_{j+1}\text{ when }j\text{ is even} \end{array}\right.\tag{5}$$ Obviously, $\displaystyle\lim_{n\to\infty}\alpha_n=0$.

Using telescoping products, it is not difficult to show that $$\frac{A_{n_{j+1}}}{A_{n_j}}=\left\{\begin{array}{} \frac{n_j}{n_{j+1}}=2^{-j-1}&\text{when }j\text{ is odd}\\ \frac{n_{j+1}}{n_j}=2^{j-1}&\text{when }j\text{ is even} \end{array}\right.\tag{6}$$ Equation $(6)$ yields $$A_{n_j}=\left\{\begin{array}{} 2^{-(j-1)/2}&\text{when }j\text{ is odd}\\ 2^{-(3j-2)/2}&\text{when }j\text{ is even} \end{array}\right.\tag{7}$$ Furthermore, using the standard formula for the partial harmonic series, when $j$ is odd, \begin{align} \sum_{n=n_j}^{n_{j+1}-1}\alpha_n &=\log\left(\frac{n_{j+1}}{n_j}\right)+O\left(\frac{1}{n_j}\right)\\ &=(j+1)\log(2)+O\left(2^{-j(j-1)/2}\right)\tag{8} \end{align} and when $j$ is even, \begin{align} \sum_{n=n_j}^{n_{j+1}-1}\alpha_n &=-\log\left(\frac{n_{j+1}}{n_j}\right)+O\left(\frac{1}{n_j}\right)\\ &=-(j-1)\log(2)+O\left(2^{-j(j-1)/2}\right)\tag{9} \end{align} Combining $(8)$ and $(9)$ yields $$\sum_{n=1}^{n_j-1}\alpha_n=\left\{\begin{array}{} \frac{j-1}{2}\log(2)+O(1)&\text{when }j\text{ is odd}\\ \frac{3j-2}{2}\log(2)+O(1)&\text{when }j\text{ is even} \end{array}\right.\tag{10}$$ Equation $(10)$ says that $\displaystyle\sum_{n=1}^\infty\alpha_n=\infty$.

Define $$\beta_n=\left\{\begin{array}{} 2^{-j}&\text{when }n=n_j-1\text{ for }j\text{ even}\\ 0&\text{otherwise} \end{array}\right.\tag{11}$$ Summing the geometric series yields $\displaystyle\sum_{n=1}^\infty\beta_n=\frac13$.

Using $(3)$, we get \begin{align} u_{n_{j+1}} &=A_{n_{j+1}}\left(u_1+\sum_{k=1}^{n_{j+1}-1}\frac{\beta_k}{A_{k+1}}\right)\\ &\ge\frac{A_{n_{j+1}}}{A_{n_j}}\beta_{n_j-1}\\ &=2^{j-1}\cdot2^{-j}\\ &=\frac12\tag{12} \end{align} when $j$ is even. $(12)$ says that $\displaystyle\lim_{n\to\infty}u_n\not=0$.

-
Equation $(3)$ does not have any detectable error, but MathJax seems to have a problem. I copy it here so that it can be viewed: $$u_n=A_n\left(u_1+\sum_{k=1}^{n-1}\frac{\beta_k}{A_{k+1}}\right)\tag{3}$$ – robjohn May 3 '12 at 20:05
Many thanks to @DavideCervone for finding a work-around for the problem! The counter-example now renders. – robjohn May 5 '12 at 17:02