Landau-Symbol < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:49 Di 21.10.2014 | | Autor: | evinda |
Hallo!!!
Ich soll zeigen, dass n [mm] \cdot 2^n=O(n!) [/mm] .
Ich habe folgendes versucht:
Wir wollen zeigen, dass n [mm] \cdot 2^n=O(n!), [/mm] also, dass:
[mm] \exists [/mm] c>0 und [mm] n_0 \geq [/mm] 0 , sodass [mm] \forall [/mm] n [mm] \geq n_0:
[/mm]
n [mm] \cdot 2^n \leq [/mm] c [mm] \cdot [/mm] n!
n [mm] \cdot 2^n \leq [/mm] n [mm] \cdot [/mm] 2 [mm] \cdot [/mm] 3 [mm] \cdots [/mm] n=n [mm] \cdot [/mm] n!, [mm] \forall [/mm] n [mm] \geq [/mm] 0
Wir nehmen c=n und [mm] n_0=0, [/mm] und haben dass n [mm] \cdot 2^n=O(n!).
[/mm]
Ist das was ich versucht habe richtig? Und habe ich es richtig formuliert?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:50 Di 21.10.2014 | | Autor: | andyv |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo,
so funktioniert das nicht. Was soll denn n in c=n sein?
Zeige, dass die Folge $(a_n)$ mit $a_n=\frac{2^n}{(n-1)!$ (nach oben) beschränkt ist.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:05 Di 21.10.2014 | | Autor: | evinda |
Ich habe nochmal überlegt. Könnte man es vielleicht so machen?
n [mm] \cdot 2^n=n \cdot [/mm] 2 [mm] \cdot [/mm] 2 [mm] \cdots [/mm] 2 [mm] \leq [/mm] n [mm] \cdot [/mm] 2 [mm] \cdot [/mm] 3 [mm] \cdots [/mm] (n-1)=1 [mm] \cdot [/mm] 2 [mm] \cdot [/mm] 3 [mm] \cdots [/mm] (n-1) [mm] \cdot [/mm] n=n!
Also, nehmen wir [mm] n_0=0 [/mm] und c=1.
Oder ist es nicht richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:14 Di 21.10.2014 | | Autor: | andyv |
Das stimmt auch nicht. (Betrachte z.B. n=2)
Um es konkreter zu machen: Zeige $ [mm] \frac{2^n}{(n-1)!}\le4 [/mm] \ [mm] \forall [/mm] n [mm] \in \IN [/mm] $
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:28 Di 21.10.2014 | | Autor: | evinda |
Ich hatte ein Begriff vergessen..
Ist es so richtig:
[Dateianhang nicht öffentlich]
?
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:47 Di 21.10.2014 | | Autor: | andyv |
Diese Ungleichung ist auch falsch. (Es gilt ja nicht [mm] 2$\le [/mm] 1$.)
Eine kleinere Schranke als 4 wirst du nicht finden.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:26 Do 23.10.2014 | | Autor: | evinda |
Für welches n bekommt man 2 [mm] \leq [/mm] 1 ? :/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:34 Do 23.10.2014 | | Autor: | andyv |
Für n=2.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:49 Do 23.10.2014 | | Autor: | evinda |
Und wie könnte ich zeigen, dass [mm] \frac{2^n}{(n-1)!} \leq [/mm] 4, [mm] \forall [/mm] n [mm] \in \mathbb{N} [/mm] ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:13 Do 23.10.2014 | | Autor: | andyv |
Z.B. per Induktion.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:23 Do 23.10.2014 | | Autor: | evinda |
Wie kommt man zum Ergebnis, dass [mm] \frac{2^n}{(n-1)!} \leq [/mm] 4, [mm] \forall [/mm] n [mm] \in \mathbb{N} [/mm] ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:42 Do 23.10.2014 | | Autor: | andyv |
Das sollte man "sehen", wenn man Zähler und Nenner ausschreibt.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:56 Do 23.10.2014 | | Autor: | evinda |
Also, kann man es so machen?
Wir wollen zeigen, dass n [mm] \cdot 2^n=O(n!), [/mm] also, dass [mm] \exists [/mm] c>0 und [mm] n_0 \geq [/mm] 0, sodass [mm] \forall [/mm] n [mm] \geq n_0: [/mm] n [mm] \cdot 2^n \leq [/mm] c [mm] \cdot [/mm] n! [mm] \Rightarrow \frac{2^n}{(n-1)!} \leq [/mm] c
[mm] \frac{2^n}{(n-1)!}=\frac{2^n}{1 \cdot 2 \cdots (n-1)} \leq \frac{2^n}{1 \cdot 2 \cdot 2 \cdots 2}=\frac{2^n}{2^{n-2}}=2^2=4
[/mm]
Wir nehmen c=4, und kommen zum Ergebnis, dass n [mm] \cdot 2^n=O(n!).
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:55 Do 23.10.2014 | | Autor: | andyv |
Eine Induktion fände ich besser, um die Gleichung für alle n dingfest zu machen.
Jefenfalls stimmt das aber jetzt.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:59 Di 28.10.2014 | | Autor: | evinda |
Wie könnte man es mit Induktion beweisen?
Ich habe folgendes versucht:
- n=1: [mm] \frac{2}{0!}=2 \leq [/mm] 4
- Wir nehmen an, dass [mm] \frac{2^n}{(n-1)!} \leq [/mm] 4
- [mm] \frac{2^{n+1}}{n!}=\frac{2^n \cdot 2}{(n-1)! \cdot n} \leq [/mm] 4 [mm] \cdot \frac{2}{n}=\frac{8}{n}
[/mm]
Wenn [mm] \frac{8}{n} \leq [/mm] 4, gilt n [mm] \geq [/mm] 2, n [mm] \cdot 2^n=O(n!) [/mm] gilt aber [mm] \forall [/mm] n [mm] \geq [/mm] 1, oder nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:43 Mi 29.10.2014 | | Autor: | andyv |
n $ [mm] \cdot 2^n=O(n!) \quad [/mm] (n [mm] \to \infty)$ [/mm] ist unabhängig von n, du meinst wohl, dass $ [mm] \frac{2^n}{(n-1)!} \leq [/mm] $ 4 für alle $n [mm] \in \IN$ [/mm] gilt und die Antwort lautet ja.
Du kannst auch n=2 als Induktionsanfang nehmen, dann gilt für ein [mm] $n\ge [/mm] 2$ sicherlich $ [mm] \frac{8}{n} \leq [/mm] $ 4, also gilt $ [mm] \frac{2^n}{(n-1)!} \leq [/mm] $ 4 für [mm] $n\ge [/mm] 2$, für n=1 ebenso.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:52 Do 30.10.2014 | | Autor: | fred97 |
Ergänzend: es gilt für jedes $x [mm] \in \IR$:
[/mm]
$n [mm] \cdot x^n=o(n!) [/mm] $ für $ n [mm] \to \infty$.
[/mm]
Es gilt also
[mm] $\bruch{n*x^n}{n!} \to [/mm] 0$ für $ n [mm] \to \infty$.
[/mm]
Denn
[mm] \bruch{n*x^n}{n!}=x*\bruch{x^{n-1}}{(n-1)!} [/mm] für $n [mm] \ge [/mm] 1$.
[mm] \summe_{n=1}^{\infty}\bruch{x^{n-1}}{(n-1)!} [/mm] ist konvergent, also gilt
[mm] $\bruch{x^{n-1}}{(n-1)!}\to [/mm] 0$ für $ n [mm] \to \infty$.
[/mm]
FRED
|
|
|
|
