Is $2^{n + 1} = O(2^n)$? Is $2^{2n} = O(2^n)$?

# Part 1 Let us assume $2^{n + 1} = O(2^n)$. To prove our claim, we have to show that there exists constants $c, n_0 > 0$ such that $0 \le 2^{n + 1} \le c \cdot 2^n$ for all $n \ge n_0$.

Now, $2^{n + 1} = 2 \cdot 2^n$

So, for $n \ge 1$ and any $c \ge 2$, $0 \le 2^{n + 1} \le c \cdot 2^n$.

# Part 1 Let us assume $2^{2n} = O(2^n)$. To prove our claim, we have to show that there exists constants $c, n_0 > 0$ such that $0 \le 2^{2n} \le c \cdot 2^n$ for all $n \ge n_0$.

Now, $2^{2n} = 2^n \cdot 2^n$

If there s a $c$, such that $0 \le 2^n \cdot 2^n \le c \cdot 2^n$, then $c \ge 2^n$. But this is not possible for any arbitrarily large value of $n$.

So, our assumption leads to a contradiction, i.e $2^{2n} \ne O(2^n)$.