Vollständige Induktion (Mathe)?
Guten Abend gutefrage.net-Community!
Kurze Vorgeschichte:
Ich bin ein 14 Jähriger 9t-Klässler, dem der Matheunterricht zu langweilig bzw. der -lehrer zu dumm ist. Daher habe ich mich schon mit folgenden Themen beschäftigt:
- Trigonometrie
- Exponentialfunktion
- Komplexe Zahlen + Zusammenhang der oberen 2 Punkte
- Sinus- und Kosinussatz
- Integral- und Differentialrechnung
- Ableitungen und Stammfunktionen
- Vektoren und Matrizen
So jetzt hab ich mir ein Buch von meinem Physiklehrer, der auch Mathe unterrichtet, geliehen namens "Analysis 1 Differential- und Integralrechnung einer Veränderlichen".
1. Thema: Vollständige Induktion
Und ich hab keinen Plan was das ist und verstehe nicht was im Buch steht. Wikipediaeinträge sind sowie so unverständlich also dachte ich mir frage ich hier mal.
Vielen Dank schon mal!
2 Antworten
Du beweist etwas für ein Element, welches in einer geordneten Menge ist, die jeweils einen Nachfolger haben.
Und Du beweist, dass falls für ein Element gilt, dass es dann auch für sein Nachfolger gilt. Das hat einen schönen unendlichen Ketteneffekt.
Beispiel: Du beweist n^2 > 2n für n = 3, das ist einfach durch Einsetzen beweisbar.
und jetzt der zweite Teil, wir untersuchen den Nachfolger
(n+1)^2 = n^2 +2n + 4 > 2n + 2n +4
die Ungleichung basiert auf dem bewiesenen n^2>2n
aus der Ungleichung ergibt sich
(n+1)^2 > 4n + 4 > 2(n + 1)
damit ist es auch für n=4 bewiesen. Weil es für 4 bewiesen ist, ist es auch für 5 bewiesen usw
Anderes Beispiel:
n+n=2n, wahr für n=0
wir untersuchen den Nachfolger
(n+1)+(n+1) = n + n + 1+ 1
das n+n können wir durch 2n ersetzen, da oben für n = 0 bewiesen. Also
(n+1)+(n+1) = 2n + 2 = 2(n + 1)
damit auch für n=1 bewiesen, damit für n=2 bewiesen, da der Nachfolger sich im Beweis auf den Vorgänger stützen kann
Die vollständige Induktion ist eine Beweistechnik, die gut dafür geeignet ist, eine Aussage für alle natürlichen Zahlen zu beweisen.
Dabei ist das Vorgehen folgendermaßen:
Man fängt mit dem Induktionsanfang an und zeigt, dass die Aussage für n=1 gilt.
Dann kommt die Induktionsvorrausetzung: Dabei Nimmt man an, dass die Aussage für ein beliebiges aber festes n gilt.
Nun kommt der Induktionsschritt. Hierbei zeigt man, dass wenn die Aussage für ein belibiges n gilt (oder ggf. auch für alle natürlichen Zahlen kleinergleich n), dass es auch für den Nachfolger n+1 gilt.
Wenn man die geschafft hat, hat man bewiesen, dass etwas für alle natürlichen Zahlen gilt.
Warum ist das ganze jetzt bewiesen und warum muss man nicht mehr machen?
Wir haben beispielsweise Aussahe A und wollen wisse, ob A(6) stimmt.
Nach dem Beweis mit vollständiger Ind. soll es also auch für 6 gelten.
Wir wissen, dass die A(1) wahr ist (das ist ja schon im Induktionsanfang bewiesen worden).
Außerdem wissen wir, dass wenn A(n) stimmt auch A(n+1) stimmt (das haben wir im Induktionsschritt gezeigt).
Also gilt auch A(2) und da A(2) stimmt auch A(3). Da A(3) wahr ist, gilt auch A(4), was wiederum A(5) impliziert. Deshalb gilt auch A(6). Dieses Muster zieht sich dann durch die gesamten natürlichen Zahlen durch.
Eine Analogie der Beweismethode sind Dominosteine. Wenn du weißt, dass ein Stein umfällt, wenn sein Vorgänger fällt und du weißt, dass ein Stein umgeworfen wird, dann fallen alle Steine danach.
(So ähnlich haben wir vollständige Induktion von unserem Professor erklärt bekommen ;) )
Falls du noch Beispiele haben magst, gib bescheid.
unvollständige Induktionen sind zB empirische Beweise über Beobachtungen.
Der Beweis der Vollständigkeit der Induktion ist eine Deduktion
vollständige Induktionen setzen eine Ordnung mit Nachfolger voraus. Komplexe Zahlen sind nicht in dieser Weise geordnet. Einen Nachfolger bei rationalen oder reellen Zahlen zu bestimmen könnte ich nicht.
Es gibt Induktionen, da wird nicht der direkte Nachfolger genommen, sondern ein entfernter, zB 3n+1.
wieso heißt es "Vollständige" Induktion?
Du zeigst eine Aussagenform A(n) für n=1, und dann induktiv „wenn für alle k<n A(k), dann A(n)“. Dann hast Du A(n) für alle n∊ℕ (=vollständig) bewiesen. Dass das gilt, ist eine Eigenschaft der natürlichen Zahlen: die sind nämlich genau so definiert.
wieso kann man damit nicht 3n + 1 beweisen?
Falls Du die Collatz-Vermutung meinst: Grundsätzlich ist deren Beweis durch vollständige Induktion recht naheliegend. Aber dummerweise ist die Information, dass die Vermutung für alle k<n gilt, für den Beweis völlig unbrauchbar, dass sie auch für n gilt – oder zumindest ist der Schluss nicht offensichtlich. Theoretisch könnte es doch irgendwie klappen, aber daran sind schon so viele kluge Köpfe gescheitert, dass Du Dich damit nur beschäftigen solltest, wenn Du sehr viel Zeit und eh keine Freunde hast :)
Gibt es auch "Versionen" der Vollständigen Induktion, die für ganze, rationale, reelle oder sogar komplexe Zahlen sind?
ℤ und ℚ sind abzählbar und können dadurch in eine Reihenfolge gebracht (=durchnummeriert) werden, mit der eine vollständige Induktion über die Nummerierung möglich wird.
Die einzige mir bekannte Verallgemeinerung zur vollständigen Induktion ist die transfinite Induktion. Das kann helfen, wenn man für eine Aussage über ℤ oder ℚ keine beweistaugliche Abzählung finden kann. Das klappt aber garantiert nicht mehr für reelle Zahlen, weil ℝ nicht wohlgeordnet werden kann.
Es muss nicht mit n=1 starten, es gibt auch Fälle, bei denen man ein höheres n wählen muss.
Okay vielen vielen Dank!
Gibt es auch "Versionen" der Vollständigen Induktion, die für ganze, rationale, reelle oder sogar komplexe Zahlen sind?
Das hört sich jetzt dumm am, aber wieso kann man damit nicht 3n + 1 beweisen?
Was wäre ein Beispiel für eine Aufgabenstellumg, an der man die Vollständige Induktion verwenden kann?
Ach ja und wieso heißt es "Vollständige" Induktion? Gibt's auch unvollständige (abgesehen davon, dass man z.B. beim 2ten Schritt abbrechen könnte ;) )?