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

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

My solution is:

$2^n 2^n \leq C_{1}2^n$

$2^n \leq C_{1}$,

TRUE.

Is this correct?

-
You're saying all powers of two are bounded by a constant? – anon Apr 13 '12 at 19:04
Please, explain me, I don't understand what is what I must to prove, Thanks. – Albert Apr 13 '12 at 19:06
Is there really a constant $C_1$ such that $2^n \le C_1$ for all $n$? – André Nicolas Apr 13 '12 at 19:08
You have to figure out whether or not there exists a constant $C$ such that $2^{2n}\le C2^n$ (or equivalently as you note, $2^n\le C$) for all $n$ beyond a certain, say, $n_0$. In other words, here you have to decide whether or not the integer powers of two have an upper bound. – anon Apr 13 '12 at 19:08
@Albert: En inglés, no existe el signo de interrogación izquierdo. – Arturo Magidin Apr 13 '12 at 19:14

If $2^{2n}=O(2^n)$, then there is a constant $C$ and an integer $M$ such that for all $n\ge M$, the inequality $2^{2n}\le C 2^n$ holds.
This would imply that $2^n\cdot 2^n\le C 2^n$ for all $n\ge M$, which in turn implies $$\tag{1} 2^n\le C \quad {\bf for\ all } \quad n\ge M.$$ Can such $C$ and $M$ exist? Note the right hand side of $(1)$ is fixed, and the left hand side...
$x^n=o(y^n)$ iff $x<y$, as $(\frac{x}{y})^n\rightarrow 0$. Here 4 and 2, so no.