How to prove $n^4 = \mathcal{O}(2^n)$?
You mentioned trying induction, to no avail. However, induction does work. Let's prove by induction that for all $n \geq 6$, $$n^4 \leq \frac{81}{4} 2^n.$$
This is true for $n = 6$ (both sides are equal to 1296). Suppose that it holds for some $n \geq 6$. Then
$$
(n+1)^4 = \left(\frac{n+1}{n}\right)^4 n^4 = \left(1 + \frac{1}{n}\right)^4 n^4 \leq \left(1 + \frac{1}{6}\right)^4 n^4.
$$
You can calculate that $(7/6)^4 &lt; 2$ (equivalently, $2401 = 7^4 &lt; 2 \cdot 6^4 = 2592$). Therefore, using the induction hypothesis,
$$
(n+1)^4 &lt; 2n^4 \leq 2 \frac{81}{4} 2^n = \frac{81}{4} 2^{n+1}.
$$
Thus the inequality holds for $n+1$ as well, completing the proof by induction.