# Bounded Sequences

I came across the following problems during the course of my self-study of real analysis:

Show that the sequence $(x_n)$ defined by $x_n = 1+ \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ is unbounded.

I know a sequence $(x_n)$ is bounded if there exists a positive number $K$ such that $|x_n| \leq K$ for all $n$. So suppose for contradiction that it is bounded. Maybe we can define sequences $a_n = x_n-1$, $b_n = a_n-\frac{1}{2}$, $c_n = b_n- \frac{1}{3} \dots$ and try to come up with a contradiction?

Show that the sequence $(x_n)$ defined by $x_1 = x$, $x_{n+1} = x_{n}+ 1/x_n$ is unbounded.

Suppose for contradiction that $(x_n)$ is bounded by $K$ for all $n$. Then show that there is some $K' < K$ which is also an upper bound?

Show that the sequence $(x_n)$ defined by $x_n = 1+ \frac{1}{2!}+ \frac{1}{3!} + \dots + \frac{1}{n!}$ is bounded above by $2$.

So there is some relationship between $n!$ and $2^{n-1}$. I think $n! \geq 2^{n-1}$ and we can prove this by induction on $n$? So $x_n \leq 1+1+ \frac{1}{8} + \dots + \frac{1}{2^{n-1}}$?

-
It's relatively easy to prove that $n! \geq 2^{n-1}$ using induction, so I'd go with that. – Nicolas Villanueva Jun 22 '11 at 19:54
Problem 1: the traditional trick for this is to notice $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \cdots + \frac{1}{8} + \frac{1}{9} + \cdots + \frac{1}{16} + \cdots > 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{8} + \frac{1}{16} + \cdots + \frac{1}{16} + \cdots.$ This has to be made rigorous, of course. – Robert Haraway Jun 22 '11 at 20:04
For part 2) this and this – Aryabhata Jun 22 '11 at 20:39
For part 1) this – Aryabhata Jun 22 '11 at 21:34

1. The simplest way to show that a sequence is unbounded is to show that for any $K\gt 0$ you can find $n$ (which may depend on $K$) such that $x_n\geq K$.

The simplest proof I know for this particular sequence is due to one of the Bernoulli brothers Oresme. I'll get you started with the relevant observations and you can try to take it from there:

Notice that $\frac{1}{3}$ and $\frac{1}{4}$ are both greater than or equal to $\frac{1}{4}$, so $$\frac{1}{3}+\frac{1}{4}\geq \frac{1}{4}+\frac{1}{4} = \frac{1}{2}.$$

Likewise, each of $\frac{1}{5}$, $\frac{1}{6}$, $\frac{1}{7}$, and $\frac{1}{8}$ is greater than or equal to $\frac{1}{8}$, so $$\frac{1}{5}+\frac{1}{6}+\frac{1}{7} + \frac{1}{8} \geq \frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8} = \frac{1}{2}.$$ Now look at the fractions $\frac{1}{n}$ with $n=9,\ldots,16$; compare them to $\frac{1}{16}$; then compare the fractions $\frac{1}{n}$ with $n=17,\ldots,32$ to $\frac{1}{32}$. And so on.

See what this tells you about $x_1$, $x_2$, $x_4$, $x_8$, $x_{16}$, $x_{32}$, etc.

2. Your proposal does not work as stated. For example, the sequence $x_n = 1+\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2^{n-1}}$ is bounded by $K=10$; but it's also bounded by $K=5$. Just because you can find a better bound to some proposed upper bound doesn't tell you the proposal is contradictory. It might, if you specify that you want to take $K$ to be the least upper bound of the sequence. Even so, it's hard to establish that a sequence is unbounded that way. (Note also that you haven't really defined the sequence very well: it is undefined for $x=0$, though that is the only problem.)

To get you started: Show that if you start the sequence with $-x$ instead of $x$, then you just get the same sequence multiplied by $-1$. That is, if you fix $x\neq 0$, and you let $y_1=-x$, $y_{n+1}= y_n + (1/y_n)$, then $y_k = -x_k$; so the sequence $(x_n)$ is bounded if and only if the sequence $y_k$ is bounded, and so you may assume $x\gt 0$.

Then show that if $0\lt x\lt 1$, and you let $y_1 = \frac{1}{x}$, $y_{n+1} = y_n+(1/y_n)$, then $y_k=x_k$ for $k\geq 2$; so you may assume that $x\geq 1$.

Now you have that the sequence is increasing. If it were bounded, it would converge, say to $L\gt 0$. Then $$L = \lim_{n\to\infty}x_n = \lim_{n\to\infty}x_{n+1} = \lim_{n\to\infty}\left(x_n + \frac{1}{x_n}\right) = \lim_{n\to\infty}x_n + \frac{1}{\lim_{n\to\infty}x_n} = L+\frac{1}{L}.$$ I think that's a very big problem for $L$...

3. Yes, if you can prove that $n!\gt 2^{n-1}$ for all $n\geq 1$, then you can bound your sequence by a sequence of powers of $\frac{1}{2}$; if you can show that sequence is bounded, you'll be done. And, yes, you can prove the inequality in question by induction on $n$. It's very simple to do. But you messed up your computations later (that second $1$ should be a $\frac{1}{2}$). If $n!\geq 2^{n-1}$, then \begin{align*} x_n &= 1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots + \frac{1}{n!} \\ &\leq 1 + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots + \frac{1}{2^{n-1}}\\ &= \frac{1 - \frac{1}{2^n}}{1 - \frac{1}{2}}\\ &= \frac{2^n-1}{2^{n-1}}\\ & = 2 - \frac{1}{2^{n-1}}.\end{align*} Almost done!

-
@Arturo: For (1), $x_1+ x_2+ x_4+ x_8 + x_{16} + \dots > 1/2$. – Damien Jun 22 '11 at 20:37
@Damien: That's not nearly good enough to show the sequence is unbounded. I mean, you already knew it was greater than $1$ (since $x_1=1$), so saying it's also greater than $\frac{1}{2}$ doesn't say anything you didn't already know. Remember, you want to show that for any number $K$, you can eventually get more than $K$. – Arturo Magidin Jun 22 '11 at 20:43
@Arturo: All of those terms are $> 1/2$. So given some $K$, there exists some $N \in \mathbb{N}$ such that for all $n >N$, $a_n \geq K$. Take $N = 2K$. – Damien Jun 22 '11 at 20:52
@Damien: What you said was that the sum of all is greater than 1/2; that's true, but not useful. If you mean to say that each of the terms $x_{2^n}$ is greater than $1/2$, that's also true, but again not helpful. It's not helpful because you aren't trying to show that the sum of the $x_i$ is unbounded, you are trying to show that the $x_i$ themselves are unbounded. You are trying to show that for any $K$, you can find $N$ such that $x_N\gt K$; if all you know is that $x_{2^N}\gt 1/2$, that doesn't help you for $K=10$. – Arturo Magidin Jun 22 '11 at 20:57
@Arturo: $x_{2n}-x_{n} \geq 1/2$ for all $n$. – Damien Jun 22 '11 at 20:59

The first part was answered in Grotaur's answer. The third part you did it yourself.

For the sequence $x_{n+1}=x_n+\frac{1}{x_n}$, first note that if the first term is positive so are all the others; if the first term is negative, so are all the others. Suppose that the first term is positive, and therefore the sequence is increasing ($x_{n+1}-x_n=\frac{1}{x_n}>0$.)

Suppose now that the sequence is bounded. A bounded increasing sequence is convergent, and denote by $L$ it's limit. Take $n \to \infty$ in the recurrence relation, and see what values could $L$ have.

-
For the third part I proved that it is less than $2+a$ but not less than $2$ where $a = \frac{1}{8} + \dots + \frac{1}{2^{n-1}}$. – Damien Jun 22 '11 at 20:13
You made a too large majorisation. You have $1+\frac{1}{2!}+\frac{1}{6!}+...\leq 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...=2$. – Beni Bogosel Jun 22 '11 at 20:29
1. Consider terms $s_k = x_{2^k-1} - x_{2^{k-1}}$. Prove that $s_k\geq \frac{1}{2}$ and note that $x_{2^n}\geq s_1+s_2+...s_n\geq \frac n 2$.
-