Zeige oder widerlege, dass n! ∈ Ω(3^n)

Question

Aufgabe:

Zeigt oder widerlegt die folgende Aussage!

n! ∈ Ω(3ⁿ)  
Problem/Ansatz: Hat jemand überhaupt Ahnung wie ist die Lösung davon?

Answer 1

Aloha :)

Um zu zeigen, dass \(f\in\Omega(g)\) gilt, reicht es zu zeigen, dass \(\lim\frac{f}{g}>0\) gilt.

Für \(n\ge2\) gilt:$$\frac{n!}{3^n}=\frac{1\cdot2\cdot3\cdot4\cdots n}{3\cdot 3\cdot 3\cdot 3\cdots3}=\frac11\cdot\frac23\cdot\underbrace{\frac33\cdot\frac43\cdots\frac n3}_{\ge1}\ge\frac{1\cdot2}{3\cdot3}\ge\frac29$$Daher gilt insbesondere:$$\lim\limits_{n\to\infty}\frac{n!}{3^n}\ge\frac29>0$$Daher gilt tatsächlich: \(n!\in\Omega(3^n)\).

Comments

Vielen vielen Dank!