Prove by mathematical induction that exponentials grow faster than polynomials

Question

How to prove that for $\forall q>1$ $\forall k\in \mathbb{N}$ $\exists c>0$ $\forall \in \mathbb{N}$ $q^n≥cn^k$? I should use mathematical induction.

Answer 1

Use induction this way:

Assume that $$ q^n \ge cn^k $$ for a certain $c>0$. Then $$ q^{n+1} = q^n q \ge cqn^k \ge c(n+1)^k $$as soon as $q \ge \left(\frac{n+1}{n}\right)^k$, that is $$n> n_0 = E\left( \frac1{q^{1/k}-1}\right) + 1 $$ ($E$ is the integer part).

---

Now for $n\le n_0$ and the value of $c$: $$q^n \ge cn^k $$when $$ c = \min\left\{ \frac{q^n}{n^k}: 0\le n\le n_0 \right\} $$

Answer 2

Yes, you should use induction. You fix the values of $q$ and $k$, then consider a first case with $n=1$ (which is quite simple), then you assume the following inequality is true:

$$q^n\ge cn^k$$ For some positive value of $c$. Using that, you should be able to get a value $c'$ such that

$$q^{n+1}\ge c'(n+1)^k$$