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

Question

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.

I can't seem to get it to format correctly but its, f(n) = 2^(n+1) = Θ(2^n) — John, Mar 07 '15 at 19:51

score 3 · Answer 1 · answered Mar 07 '15 at 19:55

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.

score 2 · Answer 2 · answered Mar 07 '15 at 20:10

2

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

answered Mar 07 '15 at 20:10

evinda

7,823

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

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

2 Answers2