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

  • 0
    Many thanks to @DavideCervone for finding a work-around for the problem! The counter-example now renders.2012-05-05