# If $\rho_{n+1}\leq\rho_{n} +\sigma_n,\;\;\forall\;\;n\geq N_0,$ then prove that $\lim\rho_n=0.$

Good day, all!

Suppose $\{\rho_n\}$ and $\{\sigma_n\}$ are two sequences of non-negative real numbers such that for some real number $N_0\geq 1,$ the following recursion inequality holds:

$$\rho_{n+1}\leq\rho_{n} +\sigma_n,\;\;\forall\;\;n\geq N_0.$$

Prove that,

1. if $\sum_{n=1}^{\infty}\sigma_n<\infty,$ then $\lim\rho_n$ exists.
2. If $\sum_{n=1}^{\infty}\sigma_n<\infty,$ and $\rho_n$ has a subsequence converging to zero, then $\lim\rho_n=0.$

The first question was asked in my exam but I skipped it. I am stating the truth! Hence, I'll like to get it solved before the final exam. So please, can anyone help me? Thanks in advance.

• if the series of $\rho_n$ converges, then the limit of $\rho_n$ has to be zero, there is nothing to prove in 1 and 2. Please double-check the formulation (perhaps you need $\sigma_n$ instead ?) – Hayk May 20 '18 at 5:40
• @Hayk: Sorry, my mistake! It has been corrected! Matt A Pelto: Thanks for the edit! – Omojola Micheal May 20 '18 at 6:11
• Please give more context. Providing context not only assures that this is not simply copied from a homework assignment, but also allows answers to be better directed at where the problem lies and to be within the proper scope. Please avoid "I have no clue" questions. Defining keywords and trying a simpler, similar problem often helps. – robjohn May 20 '18 at 7:07
• a real pity about people on this forum that go straight to down voting :) ... such a community. – Matt A Pelto May 20 '18 at 7:47
• @ robjohn: This is not an assignment question. We had the third exam yesterday and the first question, .i.e. question 1, was given to us. However, I'll correct some of my words! – Omojola Micheal May 20 '18 at 7:48

Observe that once we prove assertion $1$, then the claim of $2$ follows readily. This is due to the fact, that if $\rho_n$ is convergent, than all its subsequences must be convergent, all with the same limit. Now, if we prove claim N$1$ and assume in addition that a subsequence of $\rho_n$ converges to $0$, then $\rho_n$, having the same limit as its subsequence, must converge to $0$.

We now prove claim $1$. Observe that for any $k\in \mathbb{N}$ and any $n\geq N_0$ we have $$(1) \qquad \rho_{n+k} - \rho_n = \rho_{ n + k } - \rho_{ n + k -1} + \rho_{ n + k - 1 } - \rho_{ n + k -2} +...+\rho_{n+1} - \rho_n \leq \\ \sigma_{n+k-1} +...+\sigma_n,$$ where we apply the given inequality on each term $\rho_{n+k -i} - \rho_{n+k-i-1}$, for $i=0,....,k-1$.

From the above inequality, and the fact that $\rho_n \geq 0$, we have that $\rho_n$ is a bounded sequence. Now assume, for contradiction, that it does not converge. Hence, $\rho_n$, converges to different limits along two different subseqeunces. Namely there exists $n_{k}$ and $m_k$, and non negative numbers $a_1$ and $a_2$ such that $$\rho_{n_k} \to a_1 \qquad \text{ and } \qquad \rho_{m_k} \to a_2,$$ where $a_1 \neq a_2$. From $(1)$, let us fix $n\geq N_0$, and choose $k$ such that $n+k = n_k$. Then, taking limit with respect to $k$ and using the fact that the series $\sigma_n$ converges, we get $$(2) \qquad a_1 - \rho_n \leq \sum_{i = n}^\infty \sigma_i.$$ Now take $n\to \infty$ along the second subsequence $m_k$, we obtain $a_1 - a_2 \leq 0$, since convergence of $\sum_i \sigma_i$ implies that the right hand side of $(2)$ converges to $0$.

Since the process is symmetric (we could have started with $m_k$ and not $n_k$) we obtain also that $a_2 \leq a_1$ and hence they must be equal.

This contradicts our assumption that $a_1 \neq a_2$ and hence the limit of $\rho_n$ exists.

• What is wrong with Hayk's solution? Can anyone please, explain? – Omojola Micheal May 20 '18 at 7:49
• @Mike, let's see if the voter will be able to justify it. BTW, the only place you need non-negativity of $\rho_n$ is to get a lower bound on the sequence, as otherwise without bounding $\rho_n$ from below, it can escape to $-\infty$. So, instead of requiring $\rho_n \geq 0$ the claim stays valid also for the case $\rho_n \geq -M$, for any fixed $M\geq 0$ (the same proof works). – Hayk May 20 '18 at 8:49
• I neutralized it for you! – Omojola Micheal May 20 '18 at 15:56
• Can you please, expand this line $\leq \sigma_{n+k-1} +...+\sigma_{n-1}$? Kindly explain why it is so! – Omojola Micheal May 20 '18 at 16:09
• I was thinking it should be $\leq \sigma_{n+k-1} +...+\sigma_{n-1}+\sigma_{n}$ instead! – Omojola Micheal May 20 '18 at 16:19

Put $T_n=\sum_{k=1}^n \sigma_k$. Then $T_n$ is a convergent sequence. Now put $u_n=T_{n-1}-\rho_n$. From the inequality given, we see that $u_n$ is increasing for $n$ large, and of course (as $\rho_n \geq 0$) $\leq T_{n-1}$, hence bounded, hence convergent. It is easy to finish.

From $\rho_{n+1}-\rho_n\leq \sigma_n$ we obtain $\rho_{n}- \rho_m \leq \sum_{i=m}^{n-1}\sigma _i \Longrightarrow \rho_{n} \leq \rho_m+\sum_{i=m}^{n-1}\sigma _i$.

Taking $\limsup$ in respect of $n$ we obtain $\limsup \rho _n \leq \sum_{i=m}^\infty \sigma _i +\rho _m$.

Taking now $\liminf$, we obtain $$\limsup \rho _n \leq \liminf\rho _m$$ So, $\rho_n\longrightarrow x$ where $x \in [-\infty,\infty]$. Since $\rho _n$ is non-negative and upper bounded by $\rho_0 +\sum_{i=1}^\infty \sigma _i$, we conclude that $x\in \mathbb{R}$.