Disproving big $O$ identity

Question

How can I disprove that $2^{(n^2)}=O(2^n)$?

Should I show that $\forall c >0$ we have $2^{n^2}>c\cdot 2^n$?

Answer 1

You know that

$$\lim_{n\to\infty}n^2-n=\infty$$

By definition this means for all $N>0$ there exists $M(N)>0$ such that $n>M$ implies $n^2-n>N$.

But then let $N>\log_2(c)$. Then

$$2^{n^2-n}>2^N>2^{\log_2(c)}=c.$$