How to prove that $2^n\not\in O(n^k)$ through proof by contradiction

Question

So i'm studying for a test in Algorithms and Data structures, and while looking at older tests i found this task:

Show with a proof of contradiction that for any, fixed $k$: $2^n\notin O(n^k)$.

While i do kind of know what is expected of me, i don't really know how to do or begin this. Like i know that i'm supposed to show that the opposite of this isn't true, but i don't know how to do the individual steps.

Answer 1

You want to start from the definition of the set of functions $O(f)$.

$O(f)=\{g:\Bbb N\rightarrow\Bbb N$ $ | $ $ \forall n\ge n_0$ $ \exists c\in\Bbb R$ such that $g(n)\le c.f(n) \}$

Suppose that $2^n \in O(n^k)$, which by definition of $O(n^k)$ means that $2^n \le c.n^k$ where $n\ge n_0$.

Now you can use logs to find a contradiction in the inequality.