5
$\begingroup$

I'm stuck with this exercise: I have to find for which $x$ the estimate $\displaystyle\sum\limits_{i=0}^{n}x^i=O(n)$ holds.

It seems intuitive to me that this must be the case for all $x \in (0,1)$ but proving this seems to be beyond my abilities.

I tried some different approaches like the usual $\displaystyle \lim\limits_{x\to\infty}\frac{f(x)}{g(x)} = \text{some finite value}$ with $f(x)$ the formula for the partial sums. I tried the same thing with l'Hôpital's rule. I also tried to argue that the highest exponent of the sum must be $x^n$ and therefore I can just say that this holds for all $0 < x < 1$, but that doesn't seem very convincing to me.

I am out of ideas how to solve this problem and everything I try feels wrong to me, I hope someone in this community can help me.

1 Answers 1

6

Hint: If $0\leq x\leq 1 $ then $x^i\leq 1$ so that $\left|\sum_{i=0}^n x^i\right|\leq n+1.$

For $x>1$ notice this is a geometric series and that $\sum_{i=0}^n x^i= \frac{x^{n+1}-1}{x-1}.$ Then we are then comparing $x^{n}$ to $n$.

  • 0
    Thank you very much. I'm heaving a bit of trouble to show this with the $\exists constant$ definition but, showing it with limes should be sufficient however. I'll try the to solve it again tomorrow with the constant, i am to tired now. Still thank you a lot, I don't think I would have been able to solve it without your hints.2011-05-16