7
$\begingroup$

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

  • 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..."2012-05-03
  • 0
    @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.2012-05-03
  • 0
    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.2012-05-03
  • 0
    drmath: Any luck with my answer below?2012-05-07

2 Answers 2

4

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

  • 0
    In your first step, did you intend $\leqslant$ instead of $=$?2012-05-03
  • 0
    In your third step, you seem to be assuming that $\alpha_i>0$ (so that $A_i$ is monotonic). Is that so?2012-05-03
  • 0
    @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$.2012-05-04
  • 0
    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$.2012-05-04
  • 0
    @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.2012-05-09
  • 0
    @PeterTamaroff Not quite: start from a sequence $(\alpha_n)_n$ like you said, choose another sequence $(\gamma_n)_n$, absolutely convergent, and mix them, namely let $\bar\alpha_{2n}=\alpha_n$ and $\bar\alpha_{2n+1}=\gamma_n$. Then you can tune the sign of each $\gamma_n$ to get almost any sign pattern of $(\bar\alpha_n)_n$ you want.2012-05-09
  • 0
    @Didier Oh! Now I see your nota. So $\alpha_n$ should be always positive. That's what was troubling me. If it isn't the case $\alpha_n \geq 0$ then there is not reason the sum must necessarily diverge, unless it is asymptotic to the harmonic series or it is the case $\{α_n \}$ has arbitrarily long strings of elements with the same sign (such as a diverging harmonic series). I'm not 100% sure on this so let me know.2012-05-09
3

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

  • 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} $$2012-05-03
  • 0
    Many thanks to @DavideCervone for finding a work-around for the problem! The counter-example now renders.2012-05-05