2
$\begingroup$

I have to write a proof for the following statement.

$$\log_2(n!)\in\mathcal O(n\log_2(n))$$

What approach would you recommend. I am kind of LOST trying to figure this out.

I transformed the expression to logical symbols, I end up with this final expression.

$$\exists c\in\Bbb R,\exists\beta\in\Bbb N,\forall n\in\Bbb N,n\ge\beta\Rightarrow\log_2(n!)\le c(n\log_2(n))$$

I have to use the logarithmic rules and simple induction. But I have no idea how to assume the antecedent and determine de consequent for that exercise...

$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

Hint: Show $n!\le n^n$ then use the rules for logs.

$\endgroup$
0
$\begingroup$

$\log_2(n!) = \dfrac{\ln(n!)}{\ln{2}}$

$n \log_2(n) = \dfrac{n\ln(n)}{\ln(2)}$

Using the formula from Stirling's approxmiation we have:

$\ln(n!) = n \ln(n) - n + O(\ln(n))$.

Substiuting the above formula in the first equation and taking a ratio of the first and second equations we have:

$H(n) = \dfrac{n \ln(n) - n + O(\ln(n))}{n \ln(n)} = 1 - \dfrac{1}{\ln(n)} + \dfrac{O(\ln(n))}{n\ln(n)}$.

The limit of $H(n)$ as $n \to \infty$ is 1, which indicates that

$\log_2(n!) \in \Theta(n \log_2(n)) \implies \log_2(n) \in O(n\log_2(n))$.

$\endgroup$
3
  • $\begingroup$ Hi, do you know a similar approach that involves simple induction? Basically I am not allowed yo use Stirling's. It is not a topic I've studied. $\endgroup$ Commented Nov 24, 2013 at 21:11
  • $\begingroup$ @DanielOrtizCosta I think the link posted by Betty above has some induction examples. If you can only accept example proofs using a specific method, you should really state that restriction in your question, rather than leaving it open-ended. $\endgroup$ Commented Nov 24, 2013 at 22:42
  • $\begingroup$ You are so right. I just added a detailed explanation of what I am looking for. $\endgroup$ Commented Nov 25, 2013 at 5:13

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.