The statement I am trying to prove or disprove is $(2^n)^{1/3} \in \Theta (2n)$. I think this is false so I attempted to disprove it. Below is my proof (disproof). I want to make sure that a) I am correct in my thought that the initial statement is false and b) My proof is a complete/well-formulated asymptotic proof. This is my first time writing my own proof like this so I am very unsure. I based the structure/strategy on the proof by account named Alt found at this link: Big O notation - Proving that a function is not O(n)
Any help is appreciated, thank you
Let $f(n) = (2^n)^{\frac{1}{3}}$. Suppose for contradiction that $f(n) \in \Theta (2^n)$. Then, by definition of Big-Theta, $f(n) \in \Omega (2^n)$. Then, by definition of Big-Omega, there exist positive constants $c$ and $n_0$ such that $f(n) \geq c * 2^n$ for all $n \geq n_0$. By substituting, this becomes $(2^n)^{\frac{1}{3}} = 2^{n/3} \geq c* 2^n$. Take the $log_2$ of both sides to get $log_2(2^{n/3}) = \frac{n}{3} \geq log_2(c*2^n) = log_2(c) + log_2(2^n) = log_2(c) + n$. Then, we are left with the inequality $\frac{n}{3} \geq log_2(c) + n$. Subtract $log_2(c)$ from both sides (and flip the inequality) to get $n\leq \frac{n}{3} - log_2(c)$. However, since the equality should hold for all n's and it doesn't hold for $n=\frac{n}{3} - log_2(c) + 1$,then there is a contradiction in the initial assumption. Therefore, $f(n) \not\in \Theta (2^n)$
Your work is fine. To see that $f(n) \in \Omega(2^n)$ is false, it suffices to note that $\frac{f(n)}{2^n} = 2^{-2n/3} \to 0$ as $n \to \infty$, which is essentially what you showed.