# What is the asymptotic behaviour of a sum of powers of three?

I'm more concerned with just finding big oh since that can be used to find big omega. I am also told I cannot use limits to find the answer.

I'm given: $3+9+27+\dots+3^n$. My first assumption is that $3^n = \Theta(3^n)$. The method we're supposed to use goes something like this:

$3+9+27+\dots+3^n<3^n+3^n+\dots+3^n$

Or I think that's what we're supposed to do here. I'm not sure how to simplify a sequence of repeating $3^n$ in order to find a constant C.

Any help is appreciated.

• "finding big oh since that can be used to find big omega" -- no, it can't.
– Raphael
Jul 21 '14 at 0:00

First, your assumption, I'm more concerned with just finding big oh, since that can be used to find big omega is a bit dangerous. You could indeed easily find a $O()$ upper bound for your sum, $S(n)=3^1+3^2+3^3+\cdots+3^n$ by observing that each term is less than $3^n$ so you could have $$3^1+3^2+\cdots+3^n\le \underbrace{3^n+3^n+\cdots+3^n}_{n}=n3^n=O(n3^n)$$ but that's a huge overestimate (try it for, say, $n=5$) and so will almost certainly not serve as a suitable big-Omega bound*. Instead, you could simply use the formula for a geometric series and get an exact value, but suppose you didn't know that formula (or were prohibited from simply invoking it).

On the way to finding a good estimate, you could always try this helpful idiom: We've written $S(n)=3^1+3^2+3^3+\cdots+3^n$ and so we also have $S(n+1)=3^1+3^2+3^3+\cdots+3^{n+1}$ so \begin{align} S(n+1)-3S(n)&=(3^1+3^2+\cdots+3^{n+1})-3(3^1+3^2+\cdots+3^n)\\ &=(3^1+3^2+\cdots+3^{n+1})-(3^2+3^3+\cdots++3^{n+1})\\ &= 3 \end{align} But we also know that $S(n+1)=S(n)+3^{n+1}$ so we have $$3=S(n+1)-3S(n)=S(n)+3^{n+1}-3S(n)=-2S(n)+3^{n+1}$$ and so with a little algebra we find $$S(n) = \frac{3^{n+1}-3}{2}=\frac{3}{2}(3^n-1)$$ Since we have an exact value for the sum, we can easily see that $S(n)=\Theta(3^n)$. However, if you need to establish explicit constants to show $S(n)\ge c\,3^n$ (for big-omega) and $S(n)\le d\,3^n$ (for big-o) it's not too difficult. (Hint, can you see that you can use any $d\ge 3/2$?)

$^*$As an aside, you might have been misled in your choice of replacements at the very start by the proof that $1^k+2^k+3^k+\cdots+n^k\le n^k+n^k+\cdots+n^k=n^{k+1}$ which does indeed lead to a big-Theta estimate, though for a different sum.

• Essentially, the technique is converting the sum into a recurrence without full history and then solve it.
– Raphael
Jul 21 '14 at 0:04
• This was a better explanation than my text book provided for any example. Thank you. Jul 21 '14 at 16:12

Hint: use the formula for the sum of a geometric series.

Note that, when you write $3^n + \dots + 3^n$, you have $n$ terms so that sum evaluates to $n3^n\notin\Theta(3^n)$.