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.

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?

share|improve this question

8 Answers 8

up vote 4 down vote accepted

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.

share|improve this answer

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

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

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

share|improve this answer
    
Add me at FB. +1 –  Babak S. Jan 10 '13 at 12:53

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.