If $x_n\ge0$ and $x_{n+1} \leq x_n + \frac1{n^2}$, show that: $\lim x_n$ converges.

Question

Let $x_n$ be a sequence of the type described above. It is not monotonic in general, so boundedness won't help. So, it seems as if I should show it's Cauchy. A wrong way to do this would be as follows (I'm on a mobile device, so I can't type absolute values. Bear with me.) $$\left|x_{n+1} - x_n\right| \leq \frac{1}{n^2}.$$ So, we have $$ \left|x_m -x_n\right| \leq \sum_{k=n}^{m} \frac{1}{k^2}$$ which is itself Cauchy, etc., etc. But, of course, I can't just use absolute values like that. One thing I have shown is that $x_n$ is bounded. Inductively, one may show $$ \limsup_{n \to \infty} x_n \leq x_k + \sum_{k=n}^{\infty} \frac{1}{k^2},$$ although I'm not sure this helps or matters at all. Thanks in advance.

Disclaimer I've noticed that asking a large number of questions in quick succession on this site is often frowned upon, especially when little or no effort has been given by the asker. However, I am preparing for a large test in a few days and will be sifting through dozens of problems. Therefore, I may post a couple a day. I will only do so when I have made some initial, meaningful progress. Thanks.

Answer 1

Note that $$ \lim_{n\to\infty}\sum_{k=n}^\infty\frac1{k^2}=0 $$ and for $m\gt n$, $$ a_m\le a_n+\sum_{k=n}^\infty\frac1{k^2} $$ First, take the $\limsup\limits_{m\to\infty}$: $$ \limsup_{m\to\infty}a_m\le a_n+\sum_{k=n}^\infty\frac1{k^2} $$ which must be non-negative. Then take the $\liminf\limits_{n\to\infty}$: $$ \limsup_{m\to\infty}a_m\le\liminf_{n\to\infty}a_n $$ Thus, the limit exists.

Answer 2

Here is a very elementary solution.

Let $\displaystyle y_n = x_n - \sum_{k=1}^{n-1} \dfrac{1}{k^2}$.

One has $y_{n+1} - y_n = x_{n+1} - x_n - \dfrac{1}{n^2} \leq 0$, so $(y_n)_{n \geq 1}$ is decreasing.

Moreover, $\displaystyle y_n \geq - \sum_{k=1}^{n-1} \dfrac{1}{k^2} \geq - \dfrac{\pi^2}{6}$, so $(y_n)_{n \geq 1}$ is bounded below.

So $(y_n)_{n \geq 1}$ converges to a limit $l$, and we deduce that $\displaystyle x_n = y_n + \sum_{k=1}^{n-1} \dfrac{1}{k^2}$ converges to $l + \dfrac{\pi^2}{6}$.

Answer 3

The sequence converges iff. it is Cauchy. Suppose for the sake of contradiction it is not Cauchy. Then there is some $\epsilon>0$ such that for all $N\in\Bbb N$ there exists $n\in\Bbb N$ with $|x_{N+n}-x_N|>\epsilon$. Because we know that $x_{n+1}-x_n<1/n^2$ for all $n$, I know that for large $N$ it will be true that: $$x_{N+n}-x_N<\sum_{j=N}^{N+n-1}1/j^2<\sum_{j=N}^\infty1/j^2<\epsilon$$Fix a threshold $M$ for which $\sum_{j=N}^\infty1/j^2<\epsilon$ if $N\ge M$. For $N\ge M$ it is then true that there always exists an $n\in\Bbb N$ with $x_N-x_{N+n}>\epsilon$. If $N_1:=M$, $N_2:=N_1+n_1$, $N_3:=N_2+n_2$, etc. where $n_j$ is chosen with $x_{N_j}-x_{N_j+n_j}>\epsilon$ for all $j$, we inductively get a subsequence $(y_j)_{j\in\Bbb N}:=(x_{N_j})_{j\in\Bbb N}$ with the following property: $$\forall k,j:y_j-y_{j+k}>k\epsilon$$In particular, $y_j>k\epsilon$ follows for all $j$ and all $k$. That's clearly impossible if $k>y_j/\epsilon$, so we have ourselves a contradiction. The sequence must be Cauchy and it must converge.

Exercise: from $y_j-k\epsilon>y_{j+k}$ for all $j,k$, if we drop the assumption the sequence is bounded from below, we get one of two situations: either the sequence is bounded and does converge, or we get that the sequence necessarily diverges to $-\infty$. There are a few steps I've missed there.

Answer 4

Since all $x_n\ge0$, starting from $x_1\ge0$, for all pairs such that $x_{n+1}-x_n\ge0$, it is like walking forward by one step. For all pairs such that $x_{n+1}-x_n\le0$, it is like walking backward by one step. Surely, the step sizes and step frequencies might be different for forward and backward. The question can be interpreted as,

Starting from some initial location (coordinate) $x_1\ge0$, then walk forward/backward by some steps, then walk backward/forward by some steps, and go on. Given that $x_{n+1}-x_n\le \frac1{n^2}$, shall we finally approaches to some specific point, namely, convergent?

We can group all forward steps and all backward steps into two sets

$$F=\{x_{n+1}-x_n|x_{n+1}-x_n\ge0 \},~~~B=\{x_{n+1}-x_n|x_{n+1}-x_n<0 \}$$

which satisfies

$$F\cup B=\{x_n|n\in\mathbb N\}, ~~~~~F\cap B=\emptyset$$

It is easy to see, the sum of all forward steps is bounded above, hence convergent, namely

$$\sum_{F}(x_{n+1}-x_n)\le\sum_{n=1}^\infty \frac1{n^2}=\frac{\pi^2}6$$

Next, let's see what happen to the sum of all backward steps, namely

$$\sum_{B}(x_{n+1}-x_n)=?$$

We conclude $\displaystyle\sum_{B}(x_{n+1}-x_n)$ must be finite, hence convergent. Otherwise, if $\displaystyle\sum_{B}(x_{n+1}-x_n)=-\infty$, then there exists some $N$, such that

$$\sum_{B}^{\le N}(x_{n+1}-x_n)\le -1-\frac{\pi^2}6$$

then we have

$$x_{N+1}=\sum_{n=1}^N (x_{n+1}-x_n)=\sum_{F}^{\le N}(x_{n+1}-x_n)+\sum_{B}^{\le N}(x_{n+1}-x_n)\le-1$$

which contradicts with the fact $x_n\ge0$. Now since both $\displaystyle\sum_{F}(x_{n+1}-x_n)$ and $\displaystyle\sum_{B}(x_{n+1}-x_n)$ are convergent, $\displaystyle\sum_{n=1}^\infty (x_{n+1}-x_n)$ is absolutely convergent. Therefore,

$$\lim_{k\to\infty} x_{k}=\lim_{k\to\infty}\sum_{n=1}^{k-1} (x_{n+1}-x_n)=\sum_{F}(x_{n+1}-x_n)+\sum_{B} (x_{n+1}-x_n)\longrightarrow \text{converge}$$

Answer 5

Your last equation has a couple of bugs in it: you should write $\limsup$ instead of $\lim$ because you haven't yet shown that the limit exists, and the index of summation on the righthand side should match the index in the other RHS term.

Once you fix it up, though, it'll give you what you want. Since $\sum \frac{1}{k^2}$ converges, you can make the quantity $(\limsup_n x_n) - x_k$ as small as you like by choosing $k$ large enough.

Answer 6

For $n\geq2$, we have $$x_{n+1}\leq x_n+\frac1{n^2}<x_n+\frac{1}{n(n-1)}=x_n+\frac{1}{n-1}-\frac{1}{n}.$$ This implies $$x_{n+1}+\frac{1}{n}<x_n+\frac{1}{n-1},\quad n\geq2.$$ So the sequence $\{x_n+\frac{1}{n-1}\}_{n\geq2}$ is decreasing and $x_n+\frac{1}{n-1}>0$. So the limit $$\lim_{n\to\infty}x_n=\lim_{n\to\infty}\left(x_n+\frac{1}{n-1}\right)$$ exists.

Answer 7

I think the key is to use the liminf and limsup. Call them $a$ and $b$ respectively. Suppose they are not equal. Then their difference is some $3 \varepsilon > 0$ (You'll see why I multiplied by 3 in a moment). Now I need to use the fact that the series $\frac{1}{n^2}$ converges. Choose a natural number $i$ such that $\Sigma_{n=1}^{i} \frac{1}{n^2}$ is within $\varepsilon$ of it's limit ( I.E. $< \frac{6}{\pi ^2}$ for those who care).

From here we can say the following. Some subsequence of $x_n$ converges to $a$, so we can choose some natural $j$ such that $x_j$ is within $\varepsilon$ of the liminf. Now, the sequence of $x_n$ starting at $i+j$ is bounded above by $a+2\varepsilon$. In other words, always outside of $b$ by at least $\varepsilon$. This contradicts the fact that $b$ is the limsup. So $a=b$ thus the sequence converges.

Trying to do cauchy might be hard because it's difficult to exclude a large drop in the value of any particular $x_n$. Using the fact that the series converges is crucial. I'm pretty sure you can come up with a counter example using $\frac{1}{n}$ instead.

Answer 8

If $x_n\ge0$ and $x_{n+1} \leq x_n + \frac1{n^2}$ then exists a sequence $\{s_k\}$ such that

$$ x_{n+1} + s_n^2 = x_n + \frac1{n^2} $$

now solving the recurrence we have

$$ x_n = c_0 + \sum_{k=1}^{n-1}\left( \frac {1}{k^2}-s_k^2\right)\le c_0+\sum_{k=1}^{n-1}\frac {1}{k^2}\le c_0 + \frac{\pi^2}{6} $$