# For which x does $\sum\limits_{i=0}^{n}x^i=O(n)$ hold?

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.

-

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

-
Can I just argue that if $|\sum_{i=0}^n x^i|\leq n+1$ is true then, $\lim\limits_{n\to\infty} \frac{n+1}{n}=1$ and therefore, $|\sum_{i=0}^n x^i|\subseteq n+1 \subseteq O(n)$? Do I still have to prove anything the x outside of [0,1]? –  Brutos May 16 '11 at 20:01
@Brutos: Basically. Recall the definition of Big-$O$: We write $f(x)=O(g(x))$ as $x\rightarrow \infty$ if there exists a constant $x_0$ and a constant $M$ such that $x>x_0$ implies $|f(x)|\leq M|g(x)|$. To see why $n+1=O(n)$, choose $x_0=1$, and $M=2$. In other words, $n+1\leq 2n$ for all $n\geq 1$ so that we can write $n+1=O(n)$. (assuming we are talking about $n\rightarrow \infty$) –  Eric Naslund May 16 '11 at 20:04
@Brutos: For $x>1$, you have to show that $x^n$ is not $O(n)$. For this, I suggest a proof by contradiction. Suppose that $x>1$ and $x^n=O(n)$. Then there exists $M$ and $N$ such that for all $n\geq N$ we have $x^{n}\leq Mn$. Now, why is that last line impossible as $n\rightarrow \infty$? Equivalently, why do exponentials grow faster than any polynomial? (Also note: Since we are using big-$O$ notation, I did not worry about the factor of $\frac{x}{x-1}$ since $x$ is fixed, and that is just multiplication by a constant. –  Eric Naslund May 16 '11 at 20:09
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. –  Brutos May 16 '11 at 20:40