Prove that $2^{(n^2)} = O(2^{2n} )$

Question

I know that the O notation tells me to find $n_0$ natural and $c>0$ real, so the $$2^{(n^2)} \le c*2^{2n} $$ Only step that I can think about is this: $$2^{(n^2)} \le c*2^{n+n} $$ $$2^{(n^2)} \le c*2^n*2^n $$ But I have no clue what to do next. (Some estimate?)

Do you have some hints please?

EDIT: sorry it should be $2^{(n^2)}$

Answer 1

That is impossible. Assume that you have found such a $n_0$ and $c > 0$. Then $$2^{(n-1)^2} = 2 \frac{2^{n^2}}{2^{2n}} \le 2c $$ for every $n \ge n_0$. This is clearly false since $\lim_{n \to \infty}2^{(n-1)^2} = \infty$.

Answer 2

Your claim is false because $$\dfrac{2^{n^2}}{2^{2n}}=2^{n^2-2n}\to \infty$$ as $n\to\infty.$

Answer 3

This is, in fact, not true. Given a $c$, there is some natural number $m$ such that $2^m>c$. Now, for each $n>1+2\sqrt{ m+1}$ we have $n^2>2n+m$, which gives $$ 2^{n^2}>2^{2n+m}=2^{2n}\cdot 2^m>2^{2n}\cdot c $$