Hallo :-)
Man kann es auch so zeigen, indem ich folgende Defintion der Landau-Symbolik benutze:
Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). Dann ist$$ \mathcal{O}(g):=\{f:\mathbb{N}\rightarrow \mathbb{R}:\exists \alpha>0 \ \exists n_{0} \in \mathbb{N} \ \forall n\in \N_{\geq n_0}:0\leq f(n) \leq \alpha \cdot g(n) \} $$die Menge aller Funktion \(f\), die bis auf eine Konstante \(\alpha>0\) höchstens so schnell wächst wie \(g\).
Und jetzt dazu folgende Überlegung: Will man die Gleichheit \(\mathcal{O}(\log(n^n))=\mathcal{O}(\log(n!))\) zeigen, dann genügt es aufgrund der Transitivitätseigenschaften solcher Mengen nur die Spezialfälle zu zeigen, also:
$$ (i)\log(n!)\in\mathcal{O}(\log(n^n)) \\(ii) \log(n^n) \in\mathcal{O}(\log(n!))$$
Zu (i): Für alle \(n\in \N_{\geq 0}\) ist $$ 0\leq \log(n!)=\log(n\cdot (n-1)\cdot ... \cdot 2\cdot 1)=\sum\limits_{k=1}^n \log(k)\leq \sum\limits_{k=1}^n\log(n)=n\cdot \log(n)=\log(n^n) $$
Mit \(\alpha=1, n_0=0\) gilt also für alle \(n\in \N_{\geq 0}\) stets \(0\leq \log(n!)\leq \alpha\cdot \log(n^n)\), also folgt (i).
Zu (ii): Zeige induktiv für alle \(n\in \N_{\geq 2}\) die Abschätzung \(n^n\leq (n!)^2\).
Induktionsanfang: Für \(n=2\) ist \(2^2=4\leq 4=2^2=(2!)^2\).
Induktionsvoraussetzung: Angenommen, es gibt ein festes \(n\in \N_{\geq 2}\) mit \(n^n\leq (n!)^2\).
Induktionsschritt: Dann gilt auch \((n+1)^{n+1}\leq ((n+1)!)^2\). Dies folgt durch:
$$ ((n+1)!)^2=(n+1)^2\cdot (n!)^2\stackrel{(IV)}{\geq } (n+1)^2\cdot n^n=(n+1)^2\cdot \frac{(n+1)^{n+1}}{(n+1)^{n+1}}\cdot n^n\\=(n+1)^2\cdot (n+1)^{n+1}\cdot \frac{1}{n+1}\cdot \frac{n^n}{(n+1)^n}=(n+1)\cdot (n+1)^{n+1}\cdot \left(\frac{n}{n+1}\right)^n\\=(n+1)\cdot \left(\frac{n}{n+1}\right)^n\cdot (n+1)^{n+1}=(n+1)\cdot \frac{1}{\left(1+\frac{1}{n}\right)^n}\cdot (n+1)^{n+1}\\\stackrel{(*)}{\geq }(n+1)\cdot \frac{1}{3}\cdot (n+1)^{n+1}\stackrel{n\geq 2}{\geq} (2+1)\cdot \frac{1}{3}\cdot (n+1)^{n+1}=(n+1)^{n+1}$$
(*) Es gilt für alle \(n\in \N_{\geq 1}\) stets \(\left(1+\frac{1}{n}\right)^n\leq 3\).
Wegen Monotonie von \(\log(.)\) folgt also \(\log(n^n)\leq 2\cdot \log(n!)\).
Mit \(\alpha=2, n_0=2\) gilt also für alle \(n\in \N_{\geq 2}\) stets \(0\leq \log(n^n)\leq \alpha\cdot \log(n^n)\), also folgt (iI).
