formeln zum sort., wachstum n! < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeigen Sie, dass N! exponentiell mit N wächst. Hinweis: Finden Sie eine Basis b>1, so dass [mm] b^N [/mm] < N! für hinreichend großes N. (5 Punkte) |
Hallo, habe obige aufgabe von unserem Prof auf dem Übungszettel gefunden. Habe leider keinen lösungsansatz und diese Aufgabe gibt ja nur 5 punkte so schwer kanns nicht sein. ich habe mich schon mit dem exponentiellen wachstum auseinadergesetzt und versucht mit funktionswerten der fakultät werte für die entsprechende formel zu ermitteln dabei kamn aber nur murks raus und es passte meist nur für die nächste stelle?! wie versteht ihr die aufgabe?ich denke ich war auf dem richtigen weg sozusagen die fakultät durch eine wachstumsfuktion zu nähern aber naja welche ist richtig, oder lag ich ganz falsch? was bedeutet hier hinreichencd großes N und die bedingung [mm] b^N [/mm] < N! ? für anregungen und hilfe wäre ich dankbar.
ich habe diese frage in keinem anderen forum oder auf keiner anderen website gestellt.
|
|
| |
|
Hallo honkmaster,
> Zeigen Sie, dass N! exponentiell mit N wächst.
Ich denke, damit wird es gezeigt.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:34 Do 01.05.2008 | | Autor: | honkmaster |
anscheinend bin ich total blind aber wie zeige ich das? klar n wächst, 1,2,3,4,5,6,7 die zugehörigen fakultäten auch mit 1,2,6,24,120,720,5400 klar man sieht sofort fas des exponentiell aber was mauss ich für ne basis b wählen?
|
|
|
| |
|
mir ist grade aufgefallen wäre 2 eine mögliche basis? das liegt ja immer drunter..aber naja ab bei n=7 passt auch 3 als basis hmm wenn ich jetzt 2 als basis nehme und dann ne vollst. induktion mache reicht das?
|
|
|
| |
|
Ich denke, man kann auch folgendermaßen rechnen:
[mm]b^{\left\lfloor\frac{n}{2}\right\rfloor} \le \left\lfloor\frac{n}{2}\right\rfloor^{\left\lfloor\frac{n}{2}\right\rfloor}\Leftrightarrow \left\lfloor\frac{n}{2}\right\rfloor\log_b b=\log_b\left(b^{\left\lfloor\frac{n}{2}\right\rfloor}\right)\le\left\lfloor\frac{n}{2}\right\rfloor\log_b\left\lfloor\frac{n}{2}\right\rfloor\Leftrightarrow 1\le \log_b\left\lfloor\frac{n}{2}\right\rfloor\Leftrightarrow b\le\left\lfloor\frac{n}{2}\right\rfloor[/mm]
Das heißt, für alle [mm]n\ge 4[/mm] und [mm]2\le b\le\left\lfloor\tfrac{n}{2}\right\rfloor[/mm] gilt [mm]b^{\left\lfloor\frac{n}{2}\right\rfloor}\le n![/mm]. Für [mm]n\in\{0,1\}[/mm] gilt die Ungleichung für jedes beliebige [mm]b\![/mm]. Für [mm]n\in\{2,3\}[/mm] gilt die Ungleichung z.B. für [mm]b=2\![/mm].
|
|
|
| |
|
wie kommt man den auf das [mm] \bruch{n}{2} [/mm] den überall zu stande?
|
|
|
| |
|
> wie kommt man den auf das [mm]\bruch{n}{2}[/mm] den überall zu
> stande?
Also wie gesagt: Schaue dir nochmal diesen Link an.
|
|
|
|
