Proof $\sum_{i=1}^{n}x ^i=O(n)$

53 Views Asked by At

I just started working with Big-O notation.

Proof: for which $x$ is $\sum_{i=1}^{n}x ^i=O(n)$ true.

First case: $x>1$

$\sum_{i=1}^{n}x ^i=s_n=x\frac{x^{n+1}-1}{x-1}$ and $\lim_{n->\infty} \frac{s_n}{n}= \frac{x(x^{n+1}-1)}{n(x-1)}$.

Now I used L’Hospital

$\lim_{n->\infty} \frac{\lg(x) x^{n+1}}{(x-1)}=\infty $

$\sum_{i=1}^{n}x ^i \neq O(n)$

Edit: for x =1

Is that correct? $\sum_{i=1}^{n}1 ^i=n=O(n)$ ->true

For x<1, i have no idea, how to solve it?

2

There are 2 best solutions below

0
On BEST ANSWER

Let $$f_x(n)=\sum_{i=1}^n x^i.$$ Recall that $f_x(n)\in\mathcal O(n)$ if and only if there exist $C>0$ and and a positive integer $n_0$ such that $|f_x(n)|\leqslant Cn$ for all $n\geqslant n_0$. If $|x|=1$, then clearly $|f_x(n)|=n$ so $f_x(n)\in\mathcal O(n)$. If $|x|\ne1$, then $$ f_x(n) = \frac{x(1-x^{n+1})}{1-x}.$$ If $|x|<1$, then $\lim_{n\to\infty}f_x(n)=\frac1{1-x}$, so choosing $n_0=\max\left\{1, \left\lceil\frac1{1-x} \right\rceil\right\}$ and $C=2$ we see that $f_x(n)\in\mathcal O(n)$.

If $|x|>1$, then $\lim_{n\to\infty}|f_x(n)|=\infty$, but $$\lim_{n\to\infty}\frac{|f_x(n)|}{n} = \infty,$$ as you showed, so $f_x(n)\notin\mathcal O(n)$.

0
On

No, your proof is wrong. First, it misses cases ($x \leq 1$). Second, when you compute the limits for $n \to \infty$, it is not possible for the result to depend on $n$ anymore! And, in general, you seem not to have understood what working with $O(n)$ means.

In your case, if $x \neq -1$ then your sum becomes $\frac {x^{n+1} -1} {x-1} -1$. In order for this expression to be $O(n)$ it must be bounded by some polynomial function of $n$, of degree $1$, for large $n$. Now, if $x>1$, your sum behaves like an exponential in $n$, and no such exponential (of base $>1$) can ever be bounded by polynomials. More precisely, $\lim \limits _{n \to \infty} \frac {x^n} {p(n)} = \infty$ for every polynomial function $p$ (and yes, you prove this using l'Hospital as many times as the degree of $p$, or by induction on the degree of $p$).

If $|x|<1$, then $\lim \limits _{n \to \infty} x^n = 0$, so this shows that $\frac {x^{n+1} -1} {x-1} -1$ as a function of $n$ is bounded by $1$ for large $n$, which means that your sum is $O(1)$. Since $1<n$ as polynomial functions, then in this case the behaviour is also $O(n)$.

If $x=1$, then your sum is precisely $n$, which itself is a polynomial of degree $1$ in $n$, so in this case the behaviour is again trivially $O(n)$.

If $x=-1$, then your sum becomes $-1$ or $0$, depending on how $n$ is odd or even. But in either case, the sum is bounded by $1$, so your sum is $O(1)$ and since expressions that are $O(1)$ are also $O(n)$, the sum is $O(n)$ again.

If $x<-1$ then apply the argument for $x>1$ again, with some minor modifications relating to the presence of $(-1)^n$ which does not alter the reasoning in any significant way.

Therefore, the sum that you study is $O(n)$ only for $|x| \leq 1$ and, in fact, for $x \in [-1,1)$ is is even $O(1)$.