# How to prove that $2^{n+1} = \Theta(2^n)$?

I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.

• Do you mean $2^n+1$ or $2^{n+1}$? See math notation guide.
– user147263
Mar 7, 2015 at 19:47
• I can't seem to get it to format correctly but its, f(n) = 2^(n+1) = Θ(2^n)
– John
Mar 7, 2015 at 19:51
• Include the exponent in braces like $2^{n+1}$.
– quid
Mar 7, 2015 at 19:57

You need to show that there are positive constants $c_1,c_2$ such that

$$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ for all [sufficiently large] $n$.

For the $O$ you already found the second. The first is rather easier, so I am confident you will make it with this info at hand.

An other way to see it, is to find the limit

$$\lim_{n \to +\infty} \frac{2^{n+1}}{2^n}=\lim_{n \to +\infty} \frac{2^n \cdot 2}{2^n}=\lim_{n \to +\infty} 2=2$$

It is known that if $\lim_{n \to +\infty} \frac{f(n)}{g(n)}=c \in \mathbb{R}$ then $f(n)=\Theta(g(n))$.

• Provided he really means $n \to \infty$, which he didn't say. I'm guessing (as you did) that this is what he means. Mar 7, 2015 at 20:12