Most simple way to prove $2^n \geq A n^k$? What is the most simple and less demanding way to prove that exponentials grow faster than powers? So far I have found a proof that relies on Berloulli's inequality(*) which is elegant but doesn't look intuitive or straightforward. Can we do better?
Of course you could use de L'Hopital's or Taylor's Theorems but they would require you to introduced derivatives so you couldn't use them when you are introducing these limits for the first time while you still need to claim that exponentials grow faster.
(*) Here it is:
$$
2^n=[(\sqrt{2})^n]^2=[(1+(\sqrt{2}-1))^n]^2\geq\\
[1+n(\sqrt{2}-1)]^2\geq n^2(\sqrt{2}-1)^2 
$$
and also
$$
2^n=[(\sqrt[3]{2})^n]^3=[(1+(\sqrt[3]{2}-1))^n]^3\geq\\
[1+n(\sqrt[3]{2}-1)]^3\geq n^3(\sqrt[3]{2}-1)^3 
$$
and so on...
 A: I think an easy way to think about it (and many other harder problems concerning asymptotic analysis) is to consider growth rate. The exponential sequence $\{2^{n}\}_{n=1}^{\infty}$ has a constant growth rate of 2, while the polynomial sequence $n^{k}$ has a growth rate of $\{(1+\frac{1}{n})^{k}\}$, which eventually falls below, say, 1.5. So starting from some point, the ratio of $2^{n}$ to $n^{k}$ will grow at least at the rate of $2/1.5$. Thus the ratio will outgrow any given real number.
Edit: It seems that I need to explain why it suffices to prove the asymptotic relation $n^{k}=o(2^{n})$ and here it is: note that any sequence of positive numbers that is eventually increasing has a lower bound, so there must exist an $A$ such that $2^{n}/n^{k}>A$ for all $n\in\mathbb{N}$.
Edit: If you really want an elegant closed form bound for $A$, then I guess your construction by Bernoulli's inequality is very likely the easiest. Also note that by calculating the exact $n$ at which the growth rate of $\{n^{k}\}_{n=1}^{\infty}$ falls from $>2$ to $<2$, one can get the optimal value for $A$.
A: Inspired by dxiv's comment on the OP, we can simply note that for $n\ge2k$,
$$
2^n = (1+1)^n = \sum_{j=0}^n \binom nj \ge \binom nk = \frac{n(n-1)\cdots(n-k+1)}{k!} \ge \frac{(n/2)(n/2)\cdots(n/2)}{k!} = \frac1{2^kk!} n^k.
$$
