# 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 .

-
You should stress that $\{x_n\}_n$ is bounded. Otherwise the answer is very easy. – Siminore Sep 11 '12 at 17:16
I think a better condition is $|x_{n+1}-x_n| \lt \frac 1n$ – Ross Millikan Sep 11 '12 at 19:16

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)$.

-

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.

-
This is a clean solution, but it's worth a brief explanation as to just why the solution 'resets' infinitely often (because of the divergence of the harmonic series). – Steven Stadnicki Sep 11 '12 at 18:39
@StevenStadnicki: Thanks, good suggestion; hopefully my clarification is a clarification... – copper.hat Sep 11 '12 at 18:59
I think it is, although there was a typo (matho?) in the last paragraph that I've corrected. – Steven Stadnicki Sep 11 '12 at 19:19

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.

-
As far as I understand, any counterexample should consist of a sequence for which $-\infty<\liminf_n x_n < \limsup_n x_n < +\infty$. – Siminore Sep 11 '12 at 17:18
It seems this sequence converges to $1$. It is always within $\frac 1n$ of $1$, so given $\epsilon$ I can take $N=\frac 1\epsilon$ and $|x_n-1| \lt \epsilon$ for $n \gt N$ – Ross Millikan Sep 11 '12 at 17:19
@RossMillikan So you are saying that the question itself contains conflicting assumptions? – Siminore Sep 11 '12 at 17:21
@RossMillikan, how would the sequence converge? it reaches $1$ for infinitely many $n$ and then drops to $0$ for each $n+1$. – Karolis Juodelė Sep 11 '12 at 17:23
You are right, but the jump from $1^+$ to $0$ is greater than $\frac 1n$ I had thought it was $x_n=x_{n-1}-\frac 1n$ if $x_{n-1} \gt 1$ to keep the steps small. What you need is to take lots of up steps followed by lots of down steps. – Ross Millikan Sep 11 '12 at 17:25

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$.

-
I think this needs a bit of cleanup as there is too big a jump at $2^s$ – Ross Millikan Sep 11 '12 at 17:23
@RossMillikan We are asked to find a sequence fulfilling $x_{n+1}\leq x_n + 1/n$. I agree that this could be modified to a sequence such that $|x_{n+1}-x_n| \leq 1/n$ by descending gradually in even blocks - but this was not was is in the question posted by the OP. – Martin Sleziak Sep 11 '12 at 17:36

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}$.

-