Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$$

share|improve this question
    
What have you tried? Also, is this question homework? If so, please add the "homework" tag. –  Antonio Vargas May 3 '12 at 0:34
    
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
add comment

2 Answers 2

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$.

share|improve this answer
    
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
show 2 more comments

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$.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.