Big Oh Notation: Proving that $n! \in \Omega(7^n)$

Question

Problem

I've got the following statement which I'm looking to prove:

$\log_2(n!) \in \mathcal{O}(n \cdot \log_3(n))$

The question is: how to do it?

Steps taken so far

My approach so far was to apply a few laws regarding the logarithms as follows:

$\Leftrightarrow \left(\log_2(n!)\right) \in \mathcal{O}\left(n \cdot \log_3(n)\right)$

$\Leftrightarrow \left(\log_2(n!)\right) \in \mathcal{O}\left(\log_3(n^n)\right)$

$\Leftrightarrow \left(\frac{\ln(n!)}{\ln(2)}\right) \in \mathcal{O}\left( \frac{\ln(n^n)}{\ln(3)}\right)$

$\Leftrightarrow \left(\frac{1}{\ln(2)} \cdot \ln(n!)\right) \in \mathcal{O}\left( \frac{1}{\ln(3)} \cdot \ln(n^n) \right)$

Which approximately boils down to..

$\underline{\Leftrightarrow \left(1.44 \cdot \ln(n!)\right) \in \mathcal{O}\left( 0.91 \cdot \ln(n^n) \right)}$

Unfortunately, that's still not particularly helpful. Of course, I realize that $n^n$ is going to grow much faster than $n!$. Still, the natural logarithms combined with the constants are making it hard for me to estimate which of the two terms might be the "smaller" one.

Therefore, I'd greatly appreciate your ideas. In case we can't find a fully formal proof, a more informal one would certainly be helpful nevertheless.

Answer 1

I reckon it's time to give this question a proper answer.

I'll use a proof by induction. We have to show that $n!$ grows faster or equally fast compared to $7^n$, i.e. $$ \exists n_0,c\forall n \geq n_0: n! \geq c \cdot 7^n $$

Let's choose $n=17$. That's actually the lowest $n \in \mathbb{N}$ for which the condition will hold if we choose $c=1$. It can be found by trying out several numbers in good faith. I admit I used a computer for this one.

Induction Basis: $n = 17$

We find that $17! = 355,687,428,096,000 \geq 7^{17} = 232,630,513,987,207$ so the assertion holds in this case.

Induction Step: Let the assertion hold for a certain $n \in \mathbb{N}$. We show it also holds for $n+1$. (this suffices, as the faculty is only defined over $\mathbb{N}$)

$$ \begin{align} & (n+1)! &\overset{?}{\geq} 7^{n+1} \\ \Leftrightarrow & (n+1) \cdot n! &\geq 7 \cdot 7^n \\ \end{align} $$

As we know $n \geq 17$, we quickly conclude $(n+1) > 7$, and the induction condition already gives us $n! \geq 7^n$. Therefore, our assertion holds also.