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

In order for this statement to be true, it must be true that there exist positive constants \(c\) and \(n_0\) such that

\[0 \leq 2^{n+1} \leq c2^n \ \forall \ n > n_0\]

By reducing this inequality it is apparent that selecting any \(c \geq 2\) will make this inequality hold for all \(n > 0\). So the statement \(2^{n+1} = O(2^n)\) is true.

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

In order for this statement to be true, it must be true that there exist positive constants \(c\) and \(n_0\) such that

\[0 \leq 2^{2n} \leq c2^n \ \forall \ n > n_0\]

Reducing this inequality yields \(0 \leq 2^n \leq c\). We cannot choose a positive value for \(c\) that satisfies this inequality since \(2^n\) will eventually overtake any selected constant. So the statement \(2^{2n} = O(2^n)\) is false.