سؤال

as reading the book Algorithms by Dasgupta, C.H Papadimitriou. on Page 63.

And it is well known that $\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$. There are many ways to see this. The easiest is to notice that $n! \ge (n/2)^{(n/2)}$ because $n! = 1 · 2\cdot\cdots\cdot n$ contains at least $n/2$ factors larger than $n/2$; and to then take logs of both sides. Another is to recall Stirling’s formula.

Can someone help to find the proof on $n! \ge (n/2)^{(n/2)}$, or how should we prove it ourselves? As we take log on both side, it became (assuming that its base is some number constant) $\log(n!)$ on the left side, on the right, it became $\log\left((n/2)^{(n/2)}\right)$, further simplify $(n/2)\log(n/2)$ --> $(n/2)\log(n^{-2})$, then finally on the right side: $(-n)\log(n)$. Then we completed the proof (?)

I have two questions, is the proof of $n! \ge (n/2)^{(n/2)}$ corrected? If so, how can we argue back to "$\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$", if not, how can we proof that "$\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$"?

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top