Limit of a sequence

Question

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

Answer 1

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

Answer 2

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