Prove using induction $\ln(n!)\leqslant n\ln(n)$ for $n\geqslant 1$.

Question

Base case true

$$\ln((n+1)!) = \ln(n+1)+\ln (n!)$$ Product rule But now I'm suck Idk how to prove that is less than or equal to $(n+1)\ln(n+1)$

I suggest that you do not skip the preliminaries, even when you post here. Demonstrate the base case. And tell us you inductive hypothesis. At the step you have left off, you are ready to invoke the inductive hypothesis, but where is it? And, I think that is leaving you wondering what to do next. — Doug M, Sep 10 '16 at 00:14
Isn't $$\log(n!)=\log(1)+\log(2)+\ldots+\log(n) \leq \log(n)+\log(n)+\ldots+\log(n)=n\log(n)$$ really trivial? — Jack D'Aurizio, Sep 10 '16 at 00:40

score 2 · Answer 1 · edited Sep 09 '16 at 23:52

2

Note $$\ln((n+1)!) = \ln(n+1)+\ln (n!) \le \ln (n+1)+n\ln n$$

From our inductive hypothesis. But since $\ln n$ is an increasing function, $$\ln((n+1)!) \le \ln (n+1)+n \ln n \le \ln (n+1)+n \ln (n+1)$$

This gives us that $$\ln (n+1)! \le (n+1)\ln n$$

edited Sep 09 '16 at 23:52

answered Sep 09 '16 at 23:51

S.C.B.

How you type so fast?! – Simply Beautiful Art Sep 09 '16 at 23:52
@SimpleArt I copy and paste in order to enhance my speed – S.C.B. Sep 09 '16 at 23:53
Ah... smart.... – Simply Beautiful Art Sep 09 '16 at 23:55

score 0 · Answer 2 · answered Sep 09 '16 at 23:51

0

Hint. $\ln$ is an increasing function.

answered Sep 09 '16 at 23:51

C. Falcon

score 0 · Answer 3 · answered Sep 10 '16 at 00:05

"$\ln((n+1)!) = \ln(n+1)+\ln (n!)$"

That's 90% of it.

$\ln(n!) \le n\ln(n)$

so $\ln((n+1)!) = \ln(n+1) + \ln(n!) \le \ln(n+1) + n\ln(n)$.

We need to show $\ln(n+1) + n\ln(n) \le (n+1)\ln(n+1) = \ln(n+1) + n\ln(n+1)$

But $\ln(n+1) + n\ln(n) \le \ln(n+1) + n\ln(n+1)\iff \ln(n) \le \ln(n+1)$.

So if we can show $\ln (n) \le \ln(n+1)$ we are done. [As as $e > 1$, $\ln(n1) \le \ln(n+1) \iff e^{\ln(n)} = n \le e^{\ln(n+1)} = n+1$]

3 Answers3