O - Notation | Wie beweisen?

Aufrufe: 49     Aktiv: 25.05.2021 um 19:43

0

Zeigen Sie, dass für alle natürlichen n und alle positiven reellen a gilt: an O(n!).

 

Aloha! :-)

Weiß jemand zufälligerweise wie man das da oben am Besten beweisen kann/könnte? Die Aufgabe bereitet mir schon enorme Kopfschmerzen und ich weiß leider nicht wo ich da noch anfangen soll. 

Btw. ich würde es gerne mit der Induktion beweisen, ist glaube ich wesentlich einfacher. 

Daher hier mein Ansatz bisher:

Induktionsbasis:

n = 0

a^0 = 1 = 0!

a^0 <= 0! 

 

Induktionshypothese:

Sei a^k <= k! für n = k ∈ N, R

 

Induktionsschritt:

n = k+1

z.Z.  a^k+1 <= (k+1)!


a^k <= k!

(k+1) * a^k <= (k+1) * k!

(k+1) * a^k <= (k+1)!

.....Hier komme ich nicht mehr ganz so weiter.

 

 

 

 

 

Diese Frage melden
gefragt

Punkte: 36

 

Kommentar schreiben

1 Antwort
0
Ich lese das jetzt mal als "groß-O". Bitte bei Aufgaben auf die Details achten, und sicherlich steht da nicht "für alle n" dabei.
Die zu zeigende Aussage ist laut Def (die Du sicher nachgeschlagen hast) äquivalent dazu, dass die Folge \(x_n=\frac{a^n}{n!}\) beschränkt ist. Nun schaut man mal nach, was man bei Folgen gelernt hat, wie man daran gehen kann. Es schadet auch nicht, wenn die Folge konvergiert (dann ist sie ja auch beschränkt).
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 14.12K
 

Danke, ich werde mal nachschauen und ja die Groß-O-Notation ist hier gemeint, genau. :-)

Und die Aufgabe wurde 1 zu 1 abgeschrieben, hab es extra nochmals überprüft, also dieses "für alle n" ist auf jeden Fall dabei.



Ich würde das ganze jedoch gerne mit der Induktion beweisen, da oben hab' ich schon mal angefangen, ich werde es hier nochmals posten:


Induktionsbasis:

n = 0

a^0 = 1 = 0!

a^0 <= 0!



Induktionshypothese:

Sei a^k <= k! für n = k ∈ N, R



Induktionsschritt:

n = k+1

z.Z. a^k+1 <= (k+1)!


a^k <= k!

(k+1) * a^k <= (k+1) * k!

(k+1) * a^k <= (k+1)!

.....Hier komme ich nicht mehr ganz so weiter.


  ─   user7dde99 25.05.2021 um 19:09

Induktion ist schonmal ne gute Idee. Aber dann richtig. ZUERST (vor allem anderen) sollte stehen, was zu zeigen ist. Das fehlt hier. Und es wird auch nicht so klappen.
Dann Ind. Anf.
Dann: Ind. Vor.: Es gelte für ein n: .....(Beh. einsetzen)
Ind. Beh.: Dann gilt (Beh mit n+1 einsetzen)
Ind Schluss: Hinschreiben der linken Seite der Ind.Beh., also a^(n+1). umformen, Ind. Vor. einbringen und schauen, dass man in einer Ungleichungskette durchkommt zur rechten Seite der Ind.Beh.
Du kannst es wie oben probieren, dann merkst Du schon, was noch fehlt. Ist nicht viel.
Kurz: Induktion, aber sauber, kein Durcheinander mit k und n. Bitte genau nach dem Schema. ("Ind. Vor." darf man auch "Ind.Hyp." nennen)
Das "für alle n" in einer Aussage mit O(...) ist Unsinn, da bleibe ich dabei. Man sagt ja auch nicht "die Folge x_n ist für alle n konvergent".
  ─   mikn 25.05.2021 um 19:18

Vielen Dank, ich werde mal ein Bisschen da herumprobieren und versuchen das ganze etwas deutlicher und "sauber" zu formulieren.
Ich werde es dann irgendwann wieder hier reinposten zur Kontrolle, wenn das in Ordnung ist. :-)

"Für alle n": Da kann ich leider nicht ganz mitreden, aber die Aufgaben von meinem Professor wurden schon öfters kritisiert.
  ─   user7dde99 25.05.2021 um 19:28

Ja, poste es gerne wieder hier. Du musst Dich ja nicht öffentlich mit Deinem Prof anlegen, solltest aber für Dich wissen, worum es hier geht (auch wenn er das nicht richtig weiß, so was gibt es leider).   ─   mikn 25.05.2021 um 19:43

Kommentar schreiben