vollständige induktion

Bitte ein Bit

Dir fehlt das grundlegende Verständnis der Induktion, denn im Induktionsanfang zeigt man dass die Behauptung, ich möchte sie hier B nennen, für eine Zahl n gilt. In der Induktionsannahme nimmt man an dass für ein n die Behauptung B war ist. Das Ganze schreibt man auch als B(n). Und unter dieser Annahme zeigt man dass wenn B(n) wahr ist, muss auch B(n+1) wahr sein. Denn dann kann man zeigen dass wenn B(0) wahr ist auch B(1), B(2), B(3), ... war ist.

Prof84

Bashar schrieb:

Prof84 schrieb:

Damit das 5. Peano-Axiom anwendbar ist, muss < in I oder II als wahr bewiesen werden.

Nur dass I der Induktionsanfang ist, also die Aussage für n=1. Annahmen beweist man normalerweise nicht, deshalb heißen sie ja so.

Du hast recht! Die Annahme beweist man nicht. Die machen mich hier ganz irre ...

Prof84

Bitte ein Bit schrieb:

@Prof84:

Dir fehlt das grundlegende Verständnis der Induktion, denn im Induktionsanfang zeigt man dass die Behauptung, ich möchte sie hier B nennen, für eine Zahl n gilt. In der Induktionsannahme nimmt man an dass für ein n die Behauptung B war ist. Das Ganze schreibt man auch als B(n). Und unter dieser Annahme zeigt man dass wenn B(n) wahr ist, muss auch B(n+1) wahr sein. Denn dann kann man zeigen dass wenn B(0) wahr ist auch B(1), B(2), B(3), ... war ist.

Und Dir fehlt es an Verständnis worum es hier überhaupt geht. Der Nachweis für B(n+1) ist hier nicht erbracht worden.

Natürlich beweist man die Annahme. Sonst bleibt es ja ewig nur eine Annahme.

Bashar

Prof84 schrieb:

Der Nachweis für B(n+1) ist hier nicht erbracht worden.

Doch, wenn auch nicht explizit.

(n+1)*n! < (n+1)*n^n kommt ja direkt aus der Induktionsannahme. Eine Ungleichung bleibt gültig, wenn man beide Seiten mit einer positiven Zahl multipliziert. Die restlichen Schritte sind auch alle korrekt.

Prof84

Bashar schrieb:

Prof84 schrieb:

Der Nachweis für B(n+1) ist hier nicht erbracht worden.

Doch, wenn auch nicht explizit.

(n+1)*n! < (n+1)*n^n kommt ja direkt aus der Induktionsannahme. Eine Ungleichung bleibt gültig, wenn man beide Seiten mit einer positiven Zahl multipliziert. Die restlichen Schritte sind auch alle korrekt.

Auch Du mein Sohn Bashar?! - Nö!!!

Taurin schrieb:

(n+1)! = (n+1) * n! < (n+1) * n^n < (n+1) * (n+1)^n = (n+1)^(n+1)

Das für die Obergrenze
(n+1)*n^n < (n+1)*(n+1)^n <=> n < n+1
wahr ist, sagt mir jeder aus den Kindergarten unter mir.

Das für die Untergrenze im Induktionsschritt für n+1 gilt:
(n+1)*n! < (n+1)*n^n
muss bewiesen werden. Ist egal, ob das aus der Annahme kommt oder nicht !!!
Und genau die Umformung, die diese Sache plausible macht, will ich sehen.
Ohne dem kein Beweis des Induktionsschrittes. :p

Bashar

Was meinst du mit Ober- und Untergrenze? Ich kann deiner Argumentation nicht folgen.

Xul

Prof84 schrieb:

Das für die Untergrenze im Induktionsschritt für n+1 gilt:
(n+1)*n! < (n+1)*n^n
muss bewiesen werden. Ist egal, ob das aus der Annahme kommt oder nicht !!!

Nein, muss es nicht. Der Trick im Induktionsbeweis ist, dass man die Induktionsannahme einfach postuliert. Das, was man im Induktionsschritt zeigt, ist lediglich das, was gilt, wenn die Induktionsannahme wahr ist. Ob sie wahr ist oder nicht, spielt dabei erstmal keine Rolle. Der Induktionsanfang dient dann letztlich dazu ein erstes Element zu finden, für das die Induktionsannahme zutrifft. Aus dem Induktionsschritt folgt dann, dass die Annahme auch für den Nachfolger zutrifft und für den Nachfolger des Nachfolgers, etc.

Gruß
xul

@Prof84 eine Diskussion über die Richtigkeit eines Beweises macht keinen Sinn, wenn dir die Grundlagen wie man einen Beweis führt fehlen.

Prof84

Prof84 schrieb:

Was mir noch eingefallen ist:
n! < f(n) < n^n

Wenn wir ein f(n) finden, dass wir zwischen den Termen quetschen können und dessen Umformung und Beurteilung leicht wäre, wäre der Beweis erbracht.

Nur fällt mir keiner ein.

Taurin schrieb:

Hm... ist das doch so schwer? Oder übersehe ich etwas? Dann schreibe ich es doch mal auf (auch wenn ich eigentlich nicht gerne fremde Hausaufgaben mache)

(n+1)! = (n+1) * n! < (n+1) * n^n < (n+1) * (n+1)^n = (n+1)^(n+1

Wie? Ich dachte du kommst ohne "Zwischenfunktion" aus.
Und was ist dann: (n+1) * n^n ?

Taurin hat dann eingesetzt im Induktionsschritt:
(n+1)! < f(n+1)=(n+1)* n^n < (n+1)^(n+1)

Damit ist f(n+1) die Untergrenze von (n+1)^(n+1) und die Obergrenze von (n+1)!

@Xul: Dein Argument habe ich schon ein paar Mal abgeschmettert. Weil es nicht das Thema ist! Wir sind im Induktionsschritt!

Prof84 schrieb:

Prof84 schrieb:

Was mir noch eingefallen ist:
n! < f(n) < n^n

Wenn wir ein f(n) finden, dass wir zwischen den Termen quetschen können und dessen Umformung und Beurteilung leicht wäre, wäre der Beweis erbracht.

Nur fällt mir keiner ein.

Taurin schrieb:

Hm... ist das doch so schwer? Oder übersehe ich etwas? Dann schreibe ich es doch mal auf (auch wenn ich eigentlich nicht gerne fremde Hausaufgaben mache)

(n+1)! = (n+1) * n! < (n+1) * n^n < (n+1) * (n+1)^n = (n+1)^(n+1

Wie? Ich dachte du kommst ohne "Zwischenfunktion" aus.
Und was ist dann: (n+1) * n^n ?

Taurin hat dann eingesetzt im Induktionsschritt:
(n+1)! < f(n+1)=(n+1)* n^n < (n+1)^(n+1)

Damit ist f(n+1) die Untergrenze von (n+1)^(n+1) und die Obergrenze von (n+1)!

Ja, er hat die Induktionsvoraussetzung eingesetzt! Das Ding heißt nicht umsonst Voraussetzung.

Wenn etwas fraglich ist, dann "(n+1) * n^n < (n+1) * (n+1)^n", aber das zu beweisen gehört, wenn überhaupt, in einen Hilfssatz.

ich muss prof rechtgeben: auch wenn der beweis mathematisch korrekt ist; es wird sicher einfacher zu verstehen sein, wenn man beide seiten der ungleichung auf dieselben mathematischen operatoren zurückführt, bspw. multiplikation auf beiden seiten, weil sich dann die beiden seiten besser vergleichen lassen als multiplikation (bzw. das potenzieren) auf der einen und fakultät auf der anderen seite, man sollte also verständlich machen, dass sich n^n schneller "entwickelt" als n!.

tauris beweis - zusammengefasst - sieht so aus:
behauptung: n! < n^n
beweisführung... -> beweis: (n+1)! < (n+1)^(n+1)

es sieht fast so als ob der beweis die behauptung bestätigen muss und umgekehrt, allein dass man die behauptung zuerst prüft (n=1, n=2) und von einem n, für das die behauptung bestätigt wurde, auf ein n+1 schließt macht den beweis nachvollziehbar!
aber trotzdem ziemlich mathematisch die ganze angelegenheit ...

Prof84

http://www.chemieonline.de/forum/showthread.php?t=6106
vielleicht kommt hierbei Jemanden eine Idee ...

(n+1)!           n!          n!
----------   = -------  <  ----
(n+1)^(n+1)    (n+1)^n      n^n

streng monoton fallend und zugleich stets >0, also nach unten beschränkt -
ergo konvergent! (immerhin!)

Chemiker haben immer noch die besten Ideen.
Vollständige Induktion inklusive.
Eigentlich muss noch beweisen, dass n!/n^n < 1 ist.

Bashar

He, nicht ablenken. Wir waren bei deiner Behauptung, Taurins Beweis sei unvollständig.

Bitte ein Bit

@Prof84:

Hör mal auf rumzuflamen, ich will dir schlichtweg helfen, da ich schon zweimal jemanden die vollständige Induktion erklärte. Und oftmals muss nur der Groschen fallen.

Also nochmals. Im zweiten Schritt willst du zeigen dass wenn B(n) wahr ist, dann ist auch B(n+1) wahr. Denn nur so kannst du zusammen mit dem Induktionsanfang die Induktion machen.

Also auf den Term (n+1)n! kannst du (oder bzw. must du sogar) in irgenteiner Form immer die Induktionsvorraussetzung B(n) anwenden, denn du möchtest ja zeigen dass wenn B(n) wahr ist, dann ist auch B(n+1) wahr. Also kann du natürlich die Behauptung n! < n^n für ein n anwenden. Und daraus ergibt sich natürlich die Ungleichung (n+1)n! < (n+1)n^n.

Ich hoffe damit sind alle Klarheiten beseitigt.

.filmor

Vielleicht gefällt es ihm so?

n -> n+1 (Heißt: Wir beweisen aus n! < n^n dass (n+1)! < (n+1)^(n+1))

        n! < n^n (Induktionsannahme) | * (n+1)
<=> (n+1)! < n^n * (n+1)             | multiplizieren rechte Seite mit
                                     | ((n+1)/n)^n. Das ist gleich (1 + 1/n)^n > 1
                                     | also bleibt die Ungleichung bestehen
<=> (n+1)! < (n+1)^n * (n+1) = (n+1)^(n+1)

qed

Prof84

@strippenzieher:
Schau Dir das an. Was soll man dazu noch sagen!
Am Besten nix!

Bitte ein Bit

@Prof84:

Oh leck, ich habe selten einen Menschen gesehen, welcher sich so störrisch gegen Abschätzungen wehrt. Der Ansatz für den Beweis von .filmor für B(n+1) ist zwar gut, wird aber schätzungsweise bei größeren Beweisen unbrauchbar sein, da man öfters als einmal einen Term abschätzen muss.

Ich frage mich langsam ob du überhaupt die Induktion richtig verstanden hast. Warum macht man denn den Induktionsanfang, -schritt ? Was heißt denn überhaupt Induktion ? ...

Frag doch ruhig mal nach, wenn du Dinge nicht verstehst! Es wird dich keiner steinigen wenn du sehr einfache Dinge nachfragst. Und es ist keine Schande nachzufragen was der Unterschied zwischen "genau dann wenn" und "daraus folgt" ist!

pasti

Ich weiss nicht genau wo das Verständnisproblem von einigen liegt, aber vielleicht kann ich helfen.

Es ist A priori nicht klar, dass die vollständige Induktion funktioniert bzw. mathematisch korrekt ist. Das muss man natürlich auch beweisen.

Ein Beweis findet sich z.B. hier:

http://de.wikipedia.org/wiki/Transfinite_Induktion

Prof84

pasti schrieb:

Ich weiss nicht genau wo das Verständnisproblem von einigen liegt, aber vielleicht kann ich helfen.

Es ist A priori nicht klar, dass die vollständige Induktion funktioniert bzw. mathematisch korrekt ist. Das muss man natürlich auch beweisen.

Ein Beweis findet sich z.B. hier:

http://de.wikipedia.org/wiki/Transfinite_Induktion

Guter Link. Danke!