# How to prove $n^4 = \mathcal{O}(2^n)$?

I'm new to asymptotic notations and right now I'm trying to prove that $n^4 = \mathcal{O}(2^n)$. In my current solution (written below) I used L'Hôpital's rule repeatedly, proving that the limit of $n^4/2^n$ goes to zero. Is this correct? Additionally I'm wondering whehter there is a simpler solution to this problem. I tried induction but didn't get far. If you see an easier solution I would gladly appreciate any hints.

$\lim_{n\to\infty} \frac{n^4}{2^n} = \lim_{n\to\infty} \frac{4*n^3}{2^n * ln(2)} = ..... = 0$
• There is faster solution: $n=2^{\log_2 n}$ Sep 7, 2017 at 18:29
• @Imago, he still would need to prove $1/2^{\lim_{n\to\infty}n-4\log_2 n}\rightarrow 0$. Sep 8, 2017 at 6:42
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 < 2$ (equivalently, $2401 = 7^4 < 2 \cdot 6^4 = 2592$). Therefore, using the induction hypothesis, $$(n+1)^4 < 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.