Existence of Limit of a Sequence in $\mathbb{R}$ Let $x_n$ be a bounded sequence such that $x_{n+1}\leq x_n + 1/n$ for all $n \in \mathbb{N}$.
Then prove or disprove that $\{x_n\}_n$ always converges .
I think that it is not necessarily convergent, but I could not manage to find a
counter example .
Thanks for any help .
 A: Let $x_1 = 0$. Choose $x_n$ as follows:
$$x_{n+1} = \begin{cases}
0 && x_{n} \geq 1 -\frac{1}{n}\\ x_{n} + \frac{1}{n} && \text{otherwise} \end{cases}$$
Then it is clear that $x_n \in [0,1]$ and $x_{n+1} \leq x_n +\frac{1}{n}$. Furthermore, $x_n = 0$ and $x_n \geq \frac{1}{2}$ infinitely often. Hence the sequence does not converge.
Clarification: To see why $x_n = 0$ infinitely often, suppose that for all $n \geq N$, $x_n >0$, ie, after $N$ the sequence does not get 'reset'. Then two things must be happening, first $x_{n+1} = x_n + \frac{1}{n}$, and second $x_n < 1-\frac{1}{n}< 1$. However, since $\sum \frac{1}{n}$ diverges (starting from any $n$), we must have $x_n \geq 1 $ for some $n$, which is a contradiction. Hence the sequence resets infinitely often.
Furthermore, if $n>1$ and $x_{n+1} = 0$, then $x_n \geq 1-\frac{1}{n} \geq \frac{1}{2}$. Hence the sequence satisfies $x_n \geq \frac{1}{2}$ infinitely often as well.
A: Let $H_n =\sum_{k=1}^n \frac 1k$ and $x_n = H_n-\lfloor H_n\rfloor$.
Then $0\le x_n<1$, i.e. the sequence is bounded. From $H_n<H_{n+1}=H_n+\frac 1n$, we conclude $\lfloor H_n\rfloor\le\lfloor H_{n+1}\rfloor$, hence $x_{n+1}\le x_n+\frac 1n$.
Since $H_n\to+\infty$, there are infinitely many $n\ge3$ such that $\lfloor H_n\rfloor<\lfloor H_{n+1}\rfloor$. For such $n$ we have $x_{n+1}\le\frac1n$ and $x_n\ge1-\frac1n$, hence $|x_{n+1}-x_n|\ge \frac13$. Therfore $(x_n)$ fails to be Cauchy.
Upon closer inspection, it turns out that every $x\in [0,1]$ is a limit point of $(x_n)$.
A: Let $$x_n=\frac{k}{2^{s+1}}$$
for $n=2^{s+1}+k$, $k<2^s$.
In the other words, you define the sequence separately for $\{1\}$, $\{2,3\}$, $\{4,5,6,7\}$, $\ldots$, $\{2^s,2^s+1,\ldots,2^{s+1}-1\}$.
The step between the neighbors is always $\frac1{2^{s+1}}\le \frac1{2^s+k} = \frac1n$, only at the end of each block you jump below.
Now it remains to show that this sequence is not convergent. Can you show this?

A different example could be:
$x_n=\sin t_n$ where
$$t_n=\sum_{k=1}^n \frac1k$$
is the $n$-th partial sum of the harmonic series.
You have $$|x_{n+1}-x_n| = |\sin t_{n+1}-\sin t_n| \le |t_{n+1}-t_n| = \frac1{n+1}\le \frac1n.$$
(We have used $|\sin(a-b)| \le |a-b|$, see e.g. here.)
The inequality $|x_{n+1}-x_n|\le\frac1n$ clearly implies $x_{n+1}\le x_n+\frac1n$.
A: It can diverge. Notice that $\sum \frac{1}{n} = \infty$. Therefore a sequence with such bound can still grow to any values. A divergent sequence would be
$$x_n = \begin{cases}0 && n= 0 \\
0 && x_{n-1} > 1 \\ x_{n-1} + \frac{1}{n} && \text{otherwise} \end{cases}$$
Such sequence goes in zig-zag while satisfying the condition.
A: This is essentially Karolis' answer; but its validity has been doubted.
Let $H_n:=\sum_{k=1}^n {1\over k}$ be the $n$'th harmonic number. Then $H_0=0$, and the $H_n$ grow monotonically to $\infty$. Now put
$$x_n:=\bigl\{H_n\bigr\}\ ,$$
where $\{t\}$ denotes the fractional part of $t\geq0$. Then $0\leq x_n\leq \min\{x_n+{1\over n},\ 1\}$, whence $(x_n)_{n\geq0}$ is a sequence of the required kind.
We shall prove that the sequence $(x_n)_{n\geq0}$ diverges. Let an $N\in{\mathbb N}$ be given. There is an $n$ of size about $e^N$ such that $H_{n-1}<N<H_n$. As $H_n-H_{n-1}={1\over n}$ we have $x_{n-1}\geq 1-{1\over n}$ and $x_n\leq{1\over n}$. It follows that there are infinitely many $n$ with $x_{n-1}-x_n\geq{1\over2}$.
