# How to prove this sequence converges

Here is a problem in analysis:

Suppose $x_n\geq0$ and for all $n$, there is $$x_{n+1}\leq x_n+\dfrac1{n^2}$$ Prove that $x_n$ converges.

My approach: it is easy to prove $x_m-x_n\leq \epsilon$ using telescope series. But in order to prove it is a Cauchy sequence, it has to be proved that $x_n-x_m\leq \epsilon$ too. I am not sure how to prove the second step.

• I think that this is a hard problem if you don't know how to use $\liminf$ and $\limsup$. Do you know these? – Crostul May 29 '15 at 8:43

Since $\sum\limits_{n=1}^{\infty}\dfrac1{n^2}$ converges, by Cauchy Criterion $$\forall \epsilon>0, \exists N>0, \forall m,n>N, m>n, \sum\limits_{k=n}^{m}\dfrac1{k^2}<\epsilon$$ By telescopic nature of series, for all $m,n>N, m>n$, there is $$x_m-x_n<\sum\limits_{k=n}^{m-1}\dfrac1{k^2}<\epsilon \hspace{5 mm} \text{or} \hspace{5 mm} x_m<x_n+\epsilon$$ Fix $n$, take limsup as $m\to\infty$, there is $$\varlimsup\limits_{m\to\infty}x_m\leqslant x_n+\epsilon$$ Since above holds for all $n>N$, take liminf as $n\to\infty$, there is $$\varlimsup\limits_{m\to\infty}x_m\leqslant \varliminf\limits_{n\to\infty}(x_n+\epsilon)=\varliminf\limits_{n\to\infty}x_n+\epsilon$$ Since $\epsilon$ is arbitrary, we have $$\varlimsup\limits_{m\to\infty}x_m\leqslant \varliminf\limits_{n\to\infty}x_n \hspace{5 mm} \text{or} \hspace{5 mm} \varlimsup\limits_{n\to\infty}x_n= \varliminf\limits_{n\to\infty}x_n$$ So $\lim\limits_{n\to\infty}x_n$ exists.

Note that $\displaystyle x_{n+k}\leq x_n+\frac{1}{n^2}+\cdots+\frac{1}{(n+k-1)^2}\leq x_n+\frac{1}{n^2}+\cdots$. We have

\begin{eqnarray} \varlimsup_{k\to\infty}x_{n+k}\leq x_n+\frac{1}{n^2}+\cdots \end{eqnarray} Let $\displaystyle\varepsilon(n)=\frac{1}{n^2}+\cdots$. We have $\displaystyle\lim_{n\to\infty}\varepsilon(n) =0$ as the series $\displaystyle\sum_{n=1}^\infty\frac{1}{n^2}$ is known to converge. Now taking liminf on the RHS we have (note that it makes sense to take liminf because $x_n$ is assumed to be nonnegative) \begin{eqnarray} \varlimsup_{n\to\infty}x_n=\varlimsup_{k\to\infty}x_{n+k}\leq\varliminf_{n\to\infty}(x_n+\varepsilon(n))=\varliminf_{n\to\infty}x_n+\lim_{n\to\infty}\varepsilon(n)=\varliminf_{n\to\infty}x_n \end{eqnarray} So the limsup and liminf of the sequence coincide and it converges.

Hint: $$x_1\le x_0+1$$ $$x_2\le x_1+\frac14\le x_0+1+\frac14$$ $$x_3\le x_2+\frac19\le x_0+1+\frac14+\frac19$$ $$\cdots$$ $$x_n\le x_0+\sum_{k=1}^n\frac1{k^2}.$$

• The series is not necessarily increasing. Your hint just shows that the sequence is bounded. – Crostul May 29 '15 at 8:37
• Indeed you can have $x_n=1+\dfrac{\cos{n\pi}}{2n^2}$ or something like that... – Martigan May 29 '15 at 8:39
• @Crostul: right, that's why it's called a hint. – Yves Daoust May 29 '15 at 8:46