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.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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

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

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.