How can i prove for all $k$, $n^k = \mathcal{O}(2^n)$?

Question

the problem is to prove that for all natural $k$, $n^k=\mathcal{O}(2^n)$

Ive tried induction but i dont think i solved it right (found different C for the base and the step), i also saw this post:How to prove that $n^k = O(2^n)$

but i want to solve this without Limits.

someone have any idea?

Thanks!

It should be a straightforward application of L'Hospital's rule. — Kenta S, Aug 31 '22 at 13:08
with this implementation i got to a point: 2^(klog(n)-n)<= c and im not quit sure how should i proceed — Lightbolt, Aug 31 '22 at 15:19

score 0 · Answer 1 · answered Aug 31 '22 at 13:54

Assume $k>0$ wlog. If you want to prove by induction that (for some $N$ and $C$) $$\forall n\ge N\quad n^k\le 2^nC,$$ for your "step" you will only need $\forall n\ge N\quad(n+1)^k\le2n^k$, i.e. $\forall n\ge N\quad1+\frac1n\le\sqrt[k]2$.

Just choose $N$ accordingly ($N\ge\frac1{\sqrt[k]2-1}$) and then $C$ so as to ensure your "base" ($C\ge\frac{N^k}{2^N}$).

How can i prove for all $k$, $n^k = \mathcal{O}(2^n)$?

1 Answers1