# Existence of limit for a given sequence: $x_{n+1} \le x_n + 1/{n^2}$

Let $x_n$ be a sequence in $\mathbb{R}$ such that

$$x_{n+1} \le x_n + \frac{1}{n^2}$$

Prove that $\lim x_n$ exists (it can be a real number or infinite).

I've tried to prove it using the delta-epsilon definition, limit superior and inferior, Cauchy Criterion for convergence of sequences, all kinds of convergence criteria for sequences... but nothing seems to work.

Can you help me?

• Are there any other conditions on $x_n$? As stated, I don't think the result is correct. For instance, doesn't $-1, -2, -3, ...$ satisfy the given conditions? – paw88789 Aug 13 '14 at 5:24
• When I say that lim x(n) exists, it can be a number (x(n) is convergent) or infinite (x(n) is divergent). Your example is right: it's a divergent sequence. – Epsilon Aug 13 '14 at 5:28
• It's an exercise taken from a book. I assure you it's correct. – Epsilon Aug 13 '14 at 5:48
• Do you wanna bet? – Epsilon Aug 13 '14 at 5:55
• I was wrong. Sorry. – Jack D'Aurizio Aug 13 '14 at 6:16

Assuming that the sequence $\{x_n\}_{n\in\mathbb{N}}$ has two distinct accumulation points $A$ and $B$, then $x_n$ must belong to an $\epsilon$-neighbourhood of $A$ infinitely often and do the same of an $\epsilon$-neighbourhood of $B$. However, the series $\sum_{n=1}^{+\infty}$ is convergent, so there exists a $N$ such that $\sum_{n\geq N}\frac{1}{n^2}<\frac{|A-B|}{2}$. For any $n\geq N$, the sequence is so trapped in a neighbourhood of $A$ or in a neighbourhood of $B$, contradicting the existence of two different accumulation points.

Let's define a new sequence $y_n = x_n - \displaystyle\sum_{m = 1}^{n-1}\dfrac{1}{m^2}$.

Then, $y_{n+1} = x_{n+1} - \displaystyle\sum_{m = 1}^{n}\dfrac{1}{m^2} = x_{n+1} - \dfrac{1}{n^2} - \displaystyle\sum_{m = 1}^{n-1}\dfrac{1}{m^2} \le x_n - \displaystyle\sum_{m = 1}^{n-1}\dfrac{1}{m^2} = y_n$.

Since $y_{n+1} \le y_n$ for all $n$, we have that $y_n$ is strictly decreasing.

Therefore, either $\displaystyle\lim_{n \to \infty}y_n = L$ or $\displaystyle\lim_{n \to \infty}y_n = -\infty$. Can you finish from here?

I'm assuming that you can prove that $\displaystyle\sum_{m = 1}^{\infty}\dfrac{1}{m^2}$ converges.

Let's define partial sums as: $$s_n=\sum_{k=0}^nx_n=x_0+x_1+\cdots+x_n$$ As: $$x_{n+1}\le x_n+\frac1{n^2}$$ So $$s_n=x_0+x_1+\cdots+x_n\le\left(x_0+x_1+\cdots+x_{n-1}\right)+\left[x_{n-1}+\frac1{(n-1)^2}\right]$$ Or $$s_n=\sum_{k=0}^nx_n\le nx_0+\sum_{k=1}^{n-1}\frac{n-k}{k^2}$$

• That doesn't prove anything! – Epsilon Aug 13 '14 at 5:52
• @Epsilon see now? – RE60K Aug 13 '14 at 6:28
• Your last line is false. – Andrés E. Caicedo Aug 13 '14 at 6:31
• @AndresCaicedo aha, i accidently converted '$\le$' to '$=$' – RE60K Aug 13 '14 at 6:33
• Can you please explain how the line after "So" implies the one after "Or"? – Andrés E. Caicedo Aug 13 '14 at 6:36

For $n\geq 2$, we have $\displaystyle \frac{1}{n^2}\leq \frac{1}{n(n-1)}$ hence $$x_{n+1}\leq x_n+\frac{1}{n(n-1)}=x_n+\frac{1}{n-1}-\frac{1}{n}$$ Put now $\displaystyle u_n=x_n+\frac{1}{n-1}$ .For $n\geq 2$. We have $\displaystyle u_{n+1}\leq u_n$. Now there is two possibilities: $u_n\to -\infty$, and $x_n\to -\infty$, or $u_n\to L\in \mathbb{R}$, and $x_n\to L$.

The positive part of the series $\sum_n(x_{n+1}-x_n)$ clearly converges, $$\sum_n(x_{n+1}-x_n)_+\leq\sum_{n}1/n^2.$$ It follows that $$\lim_{n\rightarrow\infty}x_n=\sum_n(x_{n+1}-x_n)=\sum_n(x_{n+1}-x_n)_+-\sum_n(x_{n+1}-x_n)_-$$ exists, possibly with the value $-\infty$.