6
$\begingroup$

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 .

  • 0
    I think a better condition is $|x_{n+1}-x_n| \lt \frac 1n$2012-09-11

5 Answers 5

1

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

6

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.

  • 0
    I think it is, althou$g$h there was a typo (matho?) in the last paragraph that I've corrected.2012-09-11
3

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

2

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

  • 1
    @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.2012-09-11
2

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.

  • 0
    @RossMillikan You formula$t$ed two different objections to this solution. Both are misleading.2012-09-11