# Prove, formally that: $\log_2 n! \ge n$ , for all integers $n>3$.

Prove, formally that: $\log_2 n! \ge n$ for all integers $n>3$.

Hint: first prove that $n! ≥2^n$, for all integers $n >3$.

So far what I have:

Base case, $n = 4$,

$4! = 24$

$2^4 = 16$.

Therefore, it is true when $n = 4$.

So how do I proceed from here?

I know I can log the whole equation which will lead to $\log_2 n!$ and $n$. But the linkage seems to be missing. Sorry for the untidiness about the math symbols. I am trying to input them correctly but apparently I am not doing it right.

-

For the induction step just note that you can assume $2^{n-1} \le (n-1)!$ as induction hypotheses, giving you (we have $2 \le 3 < n$): $$2^n = 2\cdot 2^{n-1} \le 2 \cdot (n-1)! < n \cdot (n-1)! = n!$$ By induction, now $2^n \le n!$ for any $n > 3$. Applying $\log_2$ to both sides (note that $\log_2$ is monotone), gives $$n \le \log_2 n!, \quad n > 3$$ as wanted.
Induction. You just stated the start case for $n=4$ already. The induction step then takes the statement for $n$ to $n+1$. So we have $n! > 2^n$ given. Looking at $n+1$ we get $(n+1)!=n!*(n+1)>n!*2>2^n*2 = 2^{(n+1)}$. The first inequality uses n>3. So in total $(n+1)!>2^{n+1}$ if already $n!>2^n$ and n>3, which then induces the inequality for all n>3.