Prove about big O

Question

I need to prove that: for every $$d>0,\ \epsilon>0,\ n^d=O((1+\epsilon)^n)$$

I'm trying to use the definition: $$n^d\leq c*(1+\epsilon)^n$$ but I don't know how to continue, maybe it is wrong.

Thank you for the help!

Answer 1

You need to show that there is some $M>0$ and some $N>0$ such that $\forall n\geq N$, $n^d\leq M(1+\epsilon)^n$. Pick $M=1$ and let's find $N$: $$ n^d\leq(1+\epsilon)^n\iff d\log n\leq n\log(1+\epsilon)\iff\frac{\log n}{n}\leq\frac{\log(1+\epsilon)}{d}. $$ Consider the last inequality. At $n=e$, the LHS evaluates to $\frac{1}{e}$ and for $n\geq e$, the LHS is decreasing. In fact, you can verify (e.g. with L'Hopital's Rule) that $(\log n)/n\to 0$ as $n\to\infty$. Thus, given that $d^{-1}\log(1+\epsilon)>0$, there is some $N\geq e$ so large that for all $n\geq N$, we have $(\log n)/n\leq d^{-1}\log(1+\epsilon)$.