Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question
2  
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

5 Answers 5

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer
    
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$.

share|improve this answer
    
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
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. –  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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.