0

I am looking for a rigorous proof of $\log^n(n)=o(n!)$.

I was thinking of using this property: If $f(n), g(n) \geq 1 \ \forall\in \mathbb{N}$, and $\log f(n)=o(\log g(n)),$ then $f(n)=o(g(n)).$ However, $\log^n(n)=0$ for $n=1$, so I don't know what to do. Any help is appreciated. Note that all logs are base 2 since this problem is from a computer science class.

Hodin
  • 51
  • 4

2 Answers2

1

By Stirling's approximation, $$ n!\sim\sqrt{2\pi n}\Bigl(\frac{n}e\Bigr)^n\quad\text{as}\quad n\to\infty, $$ where $\sim$ means that the ratio tends to $1$. Hence, $$ \frac{\log^nn}{n!}=\frac{\sqrt{2\pi n}(n/e)^n}{n!}\cdot\frac{\log^n n}{\sqrt{2\pi n}(n/e)^n}. $$ Since $$ \frac{\log n}{n}\to 0\quad\text{as}\quad n\to\infty $$ (see here), we have that $(\log n)/n<1/e$ for sufficiently large $n$. Hence, for sufficiently large $n$, $$ \frac1{\sqrt{2\pi n}}\biggl(\frac{e\log n}{n}\biggr)^n\le\frac1{\sqrt{2\pi n}} $$ and the right hand side goes to $0$ as $n\to\infty$.

Cm7F7Bb
  • 17,364
  • What techniques/theorems might a proof that doesn't use Stirling's approximation use? – Hodin Oct 11 '17 at 08:38
  • @user126605 I suspect there should be more elegant ways to show this, but this is the only proof that I can come up with at the moment. – Cm7F7Bb Oct 11 '17 at 08:58
0

I'll try to avoid Stirling here.

Let us take the definition of $o(\cdot)$. For any "big" $c > 1$, there is an $N$ such that for all $n > N$, $c \log^n(n) \leq n!$. We also need to know that $(n/2)^{n/2} \leq n!$. (This is a simple fact and there are many proofs on MSE)

$$ c \log^n(n) \leq n! \Longleftarrow c\log^n(n) \leq (n/2)^{n/2} $$ Taking $(\cdot)^{1/n}$ and rearranging gives $$ c\log^n(n) \leq (n/2)^{n/2} \Longleftrightarrow (c)^{1/n} \sqrt{2} \leq \frac{\sqrt{n}}{\log(n)} $$ Now clearly the RHS is increasing toward $\infty$ while the LHS is decreasing toward $\sqrt{2}$ (a bit of calculus and L'Hopital can show it), and this whatever $c$ may be. Hence this inequality must be true at some point which gives us an $N$.

Zubzub
  • 4,143
  • 1
  • 17
  • 25
  • Shouldn't it be $\log^n(n)< cn!$ instead of $c\log^n(n)\le n!$? – Riley Oct 13 '17 at 00:09
  • Well in my post, I assume $c$ to be "big". The goal is to show that however we try to make the LHS large with a multiplicative constant, the RHS will always eventually win. Putting a "big" $c$ on the RHS can only make thing easier to prove. But in the end, it's equivalent if we simply rename $c$ to be $c'=1/c$ and divide on both sides. – Zubzub Oct 13 '17 at 07:37