Proof of $\exists n_0: k^n\leq n!\quad \forall n\geq n_0$

Question

Makes total sense to me intuitively, and it's easy to check for any specific $k$, for example $k=2$:

$2^3 = 8,\quad3! = 6 \quad $ and $\quad 2^4=16, \quad 4! = 24$

$\Rightarrow2^n\leq n! \quad \forall n\geq n_0=4\quad$ since every additional factor on the right side after $n_0$ is greater than 2.

What is the proof for the general $k$ case:

$\exists n_0: k^n\leq n!\quad\forall n\geq n_0$

I would be happy to have one non-induction proof ideally, since it usually is easier to wrap my head around. An induction proof would also be useful though. Thanks!

Answer 1

You know that $\displaystyle \sum_{n=0}^\infty \frac{x^n}{n!}$ converges because of the ratio test, or even just because you've seen that it equals $e^x$ for all $x$. Thus for any $x$ you have $\dfrac{x^n}{n!} \to 0$, and in particular for any $x$ there is an index $n_x$ with the property that $n \ge n_x \implies |x^n| \le n!$.

Answer 2

Take a natural number $N$ such that $N\geqslant2k$. Then, if $n\geqslant N$,$$n!=N!\times(N+1)\times(N+2)\times\cdots\times n\geqslant N!\times(2k)^{n-N,}$$and$$N!\times(2k)^{n-N}\geqslant k^n\iff2^n\geqslant\frac{2^Nk^N}{N!}.$$So, take $n_0\in\Bbb N$ such that $n_0\geqslant N$ and that $2^{n_0}\geqslant\frac{2^Nk^N}{N!}$. If $n\geqslant n_0$, then $2^n\geqslant\frac{2^Nk^N}{N!}$, and therefore $n!\geqslant k^n$.

Answer 3

A more direct approach. It is related to the ratio test, but requires no knowledge of infinite sums or even limits.

If $f(n)=\frac{k^n}{n!}$ then for every $n,$ $$f(n+1)=\frac{k}{n+1}f(n).\tag1$$ This means if $n+1>2k,$ then $f(n+1)<\frac12f(n).$

So given any $n_1+1>2k,$ define $n_0=n_1+1+\lceil\log_2 f(n_1)\rceil.$

Then $$f(n_0)<\frac1{2^{\lceil \log_2 f(n_1)\rceil+1}}f(n_1)<1.$$

But then for $n>n_0>2k-1,$ $(1)$ also shows that $f(n)<1.$