Aufgabe:
Zeigt oder widerlegt die folgende Aussage!
n! ∈ Ω(3n) Problem/Ansatz: Hat jemand überhaupt Ahnung wie ist die Lösung davon?
Aloha :)
Um zu zeigen, dass f∈Ω(g)f\in\Omega(g)f∈Ω(g) gilt, reicht es zu zeigen, dass limfg>0\lim\frac{f}{g}>0limgf>0 gilt.
Für n≥2n\ge2n≥2 gilt:n!3n=1⋅2⋅3⋅4⋯n3⋅3⋅3⋅3⋯3=11⋅23⋅33⋅43⋯n3⏟≥1≥1⋅23⋅3≥29\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\frac293nn!=3⋅3⋅3⋅3⋯31⋅2⋅3⋅4⋯n=11⋅32⋅≥133⋅34⋯3n≥3⋅31⋅2≥92Daher gilt insbesondere:limn→∞n!3n≥29>0\lim\limits_{n\to\infty}\frac{n!}{3^n}\ge\frac29>0n→∞lim3nn!≥92>0Daher gilt tatsächlich: n!∈Ω(3n)n!\in\Omega(3^n)n!∈Ω(3n).
Vielen vielen Dank!
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos
