# Is $X_n = 1+\frac12+\frac{1}{2^2}+\cdots+\frac{1}{2^n}; \forall n \ge 0$ bounded?

Is $X_n = 1+\frac12+\frac{1}{2^2}+\cdots+\frac{1}{2^n}; \forall n \ge 0$ bounded?

I have to find an upper bound for $X_n$ and i cant figure it out, a lower bound can be 0 or 1 but does it have an upper bound?

-

HINT: The expression for $X_n$ is a finite geometric series; there’s a simple formula for the sum, from which you can easily derive an upper bound. Indeed, you can easily derive the least upper bound of all the numbers $X_n$.

Added: As Nameless points out, the use of geometric series can be avoided in this problem, but you will need to know that formula and know it well.

-

You can do what the other answers suggest using the geometric series. Here is a self contained answer:

Observe $$X_n=1+\frac12+\frac1{2^2}+\cdots+\frac1{2^n}=1+\frac12\left(1+\cdots+\frac{1}{2^{n-1}}\right)=1+\frac12\left(X_n-\frac1{2^n}\right)$$ From here you can find the closed form of $X_n$. Finding the bounds is trivial

-
I love the way you are playing with these fractions so easily, Nameless. – Babak S. Jan 3 '13 at 18:46
Yes, this is very fun and pretty. – AndrewG Jan 3 '13 at 18:46
+1 Lovely! ${}$ – Dilip Sarwate Jan 3 '13 at 22:21

Yes, indeed: $\displaystyle X_n = \frac{1}{2^0} +\frac{1}{2^1}+\frac{1}{2^2}+\cdots+\frac{1}{2^n} \;\;\forall n \ge 0,\;$ is bounded.

In fact, your sum is equivalent to the geometric series:

$$\sum_{n=0}^\infty\left(\frac{1}{2}\right)^n$$

For a geometric series, if $0 \le x \lt 1$ $$\sum_{n=0}^\infty(x)^n = \dfrac{1}{1 - x}$$

How to derive (and remember) this "formula"?

For any $x$, $\;0\le x \lt 1,\;\;\sum_{n= 0}^\infty x^n\;$ can be written as:

$$= 1 \,+\, x \,+\, x^2 \,+\, x^3 \,+\, \cdots \;=\; \frac{1}{1-x}$$

the left-hand side being a geometric series with common ratio $x$. We can derive this formula:

\begin{align} &\text{Let }X_n = 1 + x + x^2 + x^3 + \cdots. \\[4pt] &\text{Then }xX_n =x + x^2 + x^3 + \cdots. \\[4pt] &\text{Then }X_n - xX_n = 1,\text{ so }X_n(1 - x) = 1,\text{ and thus }X_n = \frac{1}{1-x}. \end{align}

In your case, $x = \dfrac12$, so the series converges to $$\dfrac{1}{1-(1/2)} = \dfrac{1}{\left(\frac{1}{2}\right)} = 2,\quad$$ which is the least upper bound of $X_n$ (and thus any $x\ge 2$ is an upperbound).

For the Lower bound, as you suggest, $\;1\,$ works fine, as does $\,0,\,$ (here, too, there are infinitely many lower bounds)

So we indeed have that $\;X_n\;$ is bounded from above and from below.

-

Hint: Calculate the sum $$\sum_{n=0}^\infty\left(\frac{1}{2}\right)^n$$ as a geometric series.

-

It is the $n$th summation of the convergent series that @anon271828 noted above. So $X_n\to 0$ when $n\to\infty$ and so it is bounded.

-

Suppose you have to walk 2 units and at each step you walk the half of the remaining distance. Then, $X_n$ is the distance you walk after $n + 1$ steps and $X_n$ is clearly bounded by 2.

-

$$1+\frac12+\frac{1}{2^2}+\cdots+\frac{1}{2^n}=1+\frac{1}{2} \cdot \frac{\left(\frac{1}{2}\right)^{n}-1}{\frac{1}{2}-1}.$$ Now it is obviously, that it is bounded.

-
Why should it be bounded? – Ned Dabby Jan 5 '13 at 16:16
@Ned, as $n$ grows, the upper part of the fraction $\frac{\left(\frac{1}{2}\right)^{n}-1}{\frac{1}{2}-1}$ exponentially decreases, and the lower part remains the same. – JMCF125 Jun 9 '13 at 16:47

$1+\frac12+\frac{1}{2^2}+\cdots+\frac{1}{2^n}=1+\frac{\frac{1}{2}((\frac{1}{2})^n-1)}{(\frac{1}{2})-1}=1+1-(\frac{1}{2})^n\leq2$ $\forall$ $n\geq0.$

-
Add me at FB. +1 – Babak S. Jan 10 '13 at 12:53