Disprove $(2^n)^{\frac{1}{3}} \in \theta(2^n)$

Question

I know we can prove this simply by saying we can't find such $c_1,c_2$ but the question asks me to prove this by proving its negation is true. (the hint of the problem says this will be hard)

We negate the definition, $\exists c_{1}, c_{2}, \forall n \geq n_{0}, c_{1} 2^{n} \leq\left(2^{n}\right)^{\frac{1}{3}} \leq c_{2} 2^{n}$, and get $\forall c_{1}, n_{0} \exists n \geq n_{0},\left(2^{n}\right)^{\frac{1}{3}} \leq c_{1} 2^{n}$.

I'm thinking of breaking $c_1$into either positive or negative case. What I felt confused about is $\forall n_0,\exists n\geq n_0$, How can we approach this? Is there any difference between this and $\exists n_0 \forall n\geq n_0$?

Answer 1

You need to show that for all constants $c_1$, and for all $n_0\in \mathbb N$, there will exist $n\ge n_0$ such that $$c_12^n> 2^{n/3}.$$ This will prove the lowed bound cannot be satisfied. This is equivalent to $n> \frac32\log_2(1/c_1)$, so simply choose $n$ to be $\max(n_0,\lceil \frac32\log_2(1/c_1)\rceil)$.

Answer 2

If $2^n \leq C (2^n)^{\frac13}$ then $2^{\frac{2n}{3}} \leq C$. This can't hold as $n\to\infty$.
In other words, $2^n$ grows faster than $2^{\frac n3}$.
It's better to try to understand problems intuitively than to write a bunch of formal symbols and get yourself mixed up.

Abstractly, $\exists y\ \forall x$ says the same $y$ works for every $x$.
Whereas $\forall y\ \exists x$ says you're allowed to pick a different $y$ for each $x$.