Prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$

Question

I need to prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$.

I believe this statement is true, so I want to prove it.

I know that $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such that $f(n) \leq C g(n)$ whenever $n > k$.

Here is what I have so far, but I get stuck at trying to simplify the fraction so as to find my constant C.

$$ \frac{f(n)}{g(n)} = \frac{2^{n+1}}{2^n} \leq \frac{2^{n+n}}{2^n}=\frac{2^{2n}}{2^n} $$

Can anybody tell me where to go from here? I think I can complete it once I find a constant $C$.

Answer 1

$ \dfrac{f(n)}{g(n)} = \dfrac{2^{n+1}}{2^n} =2 $. So $ {f(n)}\leqslant2\cdot{2^n} $, or $f(n)=O(2^n)$

Answer 2

Hint: This follows from $2^{n+1}=2\cdot 2^n.$

Answer 3

I think you need to take a different approach.

The thing to realize is that

$$f(n) = 2^{n+1} = 2 \cdot 2^n \leq 2 \cdot 2^n$$

for all $n \in \mathbb{N}$, and so $f(n) \in O(2^n)$.