Wieso ist die vollständige Induktion ein Beweis, wenn man für den Beweis davon ausgehen muss, dass die Bedingung für alle n gilt (Induktionsannahme)?

... komplette Frage anzeigen

6 Antworten

Hihi, da fallen fast alle (inklusive ich) drauf rein. Vorab, Vollständige Induktion ist ein Beweisverfahren welches man von einem
bestimmten Bezugspunkt aus betrachten muss. Genauso wie bei Termen, wenn
man sich nicht vorstellt das dahinter jede Zahl stehen kann, bleiben
sie ein unlösbares Rätsel. :) Aber nur durch diese Vorstellung kann man
Mathematik machen.

Ich finde die Veranschaulichung mit den
Dominosteinen nicht so toll, da wenn der erste Stein umfällt, ja dann
schon alle anderen umfallen. ._.

Der mit einer Leiter ist meiner Meinung nach besser, auf diesen werde ich im weiteren Verlauf genauer eingehen.

Vorab
sollte man sich den Peano-Axiomen bzw. der Struktur der natürlichen
Zahlen bewusst sein. Die Beweismethode ist letztendlich eine Folgerung
aus Peano 5, dem fünften und letzten Axiom. Ich weiß leider nicht wie
weit Du bist hinsichtlich Unimathematik. Also ob Du schon die
Aussagenlogik und Mengenlehre kennst. Deshalb nur die ersten vier Peano
Axiome, die Folgerung ist für das Verständnis meiner Ansicht nach
unwichtig.

1. 0 ist Element der natürlichen Zahlen.

2. Jede natürliche Zahl hat einen Nachfolger, der auch eine natürliche Zahl ist.

3. 0 ist die kleinste natürliche Zahl.

4. Jede unterschiedliche natürliche Zahl besitzt einen anderen Nachfolger.

Vollständige Induktion funktioniert nun so.

---

I.B (Induktionsbeginn): Zeige das die Aussage für das kleinste Element der natürlichen Zahlen gilt, also für die 0.

Das zeigt man dann einfach per Hand.

---

I.A (Induktionsannahme): Wir
nehmen mal an, die Aussage gelte für irgendein konkretes k aus den
natürlichen Zahlen. Wir nehmen diesen Fall also einfach nur mal an,
soweit okay?

Achtung: Wir nehmen ihn nicht für jede
natürliche Zahl an, dann wäre das was wir im nächsten Schritt zeigen
Schwachsinn. Denn der Nachfolger einer natürlichen Zahl wäre ja wieder
eine natürliche Zahl, kapiert?

I.S (Induktionsschritt): Unter der Annahme, das die Aussage für ein festes aber beliebiges k gilt, wollen wir nun beweisen, dass die Aussage für den Nachfolger von k gilt, also k+1.

=> Also wenn es für eine natürliche Zahl gilt, dann auch für dessen Nachfolger.

---

Jetzt überlegen wir mal wieso wir den Induktionsbeginn gemacht haben. Wir wissen es gilt für die 0, durch den I.B.

Aufgepasst,
wir wissen es gilt für die 1, durch den I.S. Weil wenn es für eine
natürliche Zahl gilt, dann ja auch für dessen Nachfolger. Und jetzt gilt
es ja für eine natürliche Zahl, nämlich der Null. :) Also gilt es für
die 1. Jetzt wissen wir das ja jede natürliche Zahl einen Nachfolger
hat, und dieser wieder eine natürliche Zahl ist. Demnach gilt die
Aussage für die 2, da es ja für die 1 gilt.

Und das geht immer so weiter, abstrakt in einem Schlag ist die Aussage für alle natürlichen Zahlen bewiesen.

Vielleicht hilft es sich vorzustellen, das der Teil mit dem Induktionsschritt ein sozusagen abgeschlossenes System ist.

---

Veranschaulichung:

Nun
zur der mit den Leitern. Du zeigst das Du auf die erste Stufe steigen
kannst, alles klar. Als nächstes, wenn Du auf eine Stufe steigen kannst,
dann auf dessen nächste. Ist sehr simpel. Ich mag generell
Illustrationen selten, da sie nichts mehr mit der Mathematik zu tun
haben.

Beispiel:

Für alle natürlichen Zahlen gilt:

1+3+5+...+(2i-1) = n²

Was heißt das im Detail?

Am
Anfang ist für (2i-1) i = 1. Also 2*1-1 = 1; i ist immer eine
natürliche Zahl, merkst Du was? Jede natürliche Zahl mit 2 multipliziert
ist immer gerade, wenn man jetzt eine wegnimmt, dann ist diese
ungerade. Und für i = 1 ist das die 1, i = 2, die 3 usw.

Herleitung:

1+3+5 = 3²

9 = 9

1+3+5+7 = 4²

16 = 16

Als
Mathematiker hat man hier also eine Struktur/Muster entdeckt. Wir
können das für andere Zahlen probieren, aber wir können es ja nicht für
alle natürlichen Zahlen machen. Geht ja schlecht, brauchen wir ja
unendlich lang. ^^

Zuvor wir zum Beweis kommen, müssen wir noch eine Sache formalisieren.

f sei eine ungerade natürliche Zahl, für alle f in IN gilt:

f1+f2+f3+...+(2i-1) = n²

Wir nehmen also n mal aufeinander folgende natürliche ungerade Zahlen.

Wenn
n = 1 ist, dann setzen wir für i = 1 ein und das war´s. Wenn n = 2 ist,
dann setzen wir für i = 1 ein, rechnen das aus und addieren dies mit
2i-1 für i = 2. Soweit denke ich klar. Wenn n = n ist, dann setzen wir n
mal entsprechendes ein und addieren das alles miteinander.

Beweis:

I.B: 2*1-1 = 1 = 1²

---

I.A: 1+3+5+...+(2i-1) = n²

Wir
müssen nun das Prinzip der Induktion hieraus übertragen. Wir nehmen an,
dass wenn wir n-mal die Summe nehmen (feste aber beliebige Anzahl), es
dann auch für dessen Nachfolger gilt.

I.S: 1+3+5+...+(2i-1)+(2i+1) = (n+1)²

Hier
müssen wir ja überlegen, was der ungerade Nachfolger einer ungeraden
natürlichen Zahl (2i-1) ist. Einfach indem wir 1 beim Produkt addieren
und nicht abziehen. Wir addieren dann also n+1-mal. :)

Fangen wir also an.

1+3+5+...+(2i-1)+(2i+1) = n²+(2i+1)

Das
geht durch die Induktionsannahme. Überlege was wir zeigen wollen. ;)
Wenn ja wie angenommen die Aussage für ein n bereits gilt, können wir
sie eben auch benutzen. Wir wollen ja lediglich zeigen es gilt unter
dessen Voraussetzung.


n²+2i+1 = (n+1)²

Unter der
Verwendung der ersten binomischen Formel. Lass Dich nicht von den
verschiedenen Buchstaben verwirren lassen, ist das der Fall denke über
dessen Zusammenhang nach.

Wir sind mit dem Beweis fertig, wir zeigten das sie für die 1 gilt und wenn es für ein n gilt, dann auch für dessen Nachfolger.

---

Das sollte alles gewesen sein, um vollständige Induktion verstanden zu haben.

Die
Beweismethode funktioniert übrigens auch für alle ganzen Zahlen. Man
zeigt die Eigenschaft für die natürlichen Zahlen, durch Induktion und
für die negativen ganzen Zahlen. Darauf kann man leicht selbst kommen,
wenn man das Prinzip oben vollkommen verstanden hat.

Im Anhang
sind zwei Bilder, einmal die Formalisierung des Induktionsbeweis für die
natürliche Zahlen und im anderen für alle ganzen Zahlen.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Naydoult
17.10.2016, 14:52

Im Anhang beim zweiten Bild ist mir ein kleiner Fehler unterlaufen, den jeder aber bestimmt selbst bemerkt. Bei den negativen ganzen Zahlen kommt (A(k) => A(k-1)), habe geschrieben: (A(k) => A(-1)), ist natürlich Blödsinn. :D

0

Man muss ja einen Anfangswert haben, für den die Bedingung gilt. Zeigt man jetzt, dass die Bedingung auch für n+1 gilt, wenn sie für n gilt, so kann man sich vom Anfangswert Schritt für Schritt hochangeln.

Antwort bewerten Vielen Dank für Deine Bewertung

Es geht um vollständige Induktion. Du hast einen Anfang. Du erbringst also den Nachweis, dass die Regel für ein Elemnt  gilt.

Dann beweist man, dass man von jedem beliebigen Element auf ein weiteres folgedndes Element schließen kannst. Damit schließt Du von einem auf alle anderen Elemente.

Antwort bewerten Vielen Dank für Deine Bewertung

Wieso ist die vollständige Induktion ein Beweis, wenn man für den Beweis davon ausgehen muss, dass die Bedingung für alle n gilt (Induktionsannahme)? […] Die Induktionsannahme (Gültigkeit für alle n) kann doch falsch sein.. wo ist da der Beweis, wenn man auf dieser Basis die Gültigkeit für n+1 prüft?

Du irrst dich. Angenommen, wir wollen ∀n.Φ(n) beweisen Die Annahme ist nicht ∀n.Φ(n). 

Du denkst etwa, dass man während Induktion im Endeffekt beweist:

Φ(0) UND [∀n.Φ(n)] ⟹ [∀n.Φ(n+1)]               ...(1)

Das ist ein Missverstädnis. Genau genommen, beweist man folgende Aussage:

Φ(0) UND ∀n.[Φ(n) ⟹ Φ(n+1)]                    ...(2)

Diese zwei Aussagen (1) & (2) sind völlig verschieden. Die Struktur der Argumentationsweise ist wie folgt:

 ____
| ...
| [Bla bla bla Argument/Berechnung]
| ...
| Also gilt Φ(0)
| ____
| | Sei n ∈ ℕ beliebig.
| | ____
| | | Angenommen, Φ(n) gelte. [ANNAHME]
| | | ...
| | | [Bla bla bla Argument/Berechnung]
| | | ...
| | | Also gilt Φ(n+1). |
| | ˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜
| | Daher Φ(n) ⟹ Φ(n+1). |
| ˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜
| Also gilt ∀n ∈ ℕ. [Φ(n) ⟹ Φ(n+1)] |
˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜
Darum gilt Φ(0) & ∀n∈ℕ.[Φ(n) ⟹ Φ(n+1)]
Daraus folgt ∀n∈ℕ.Φ(n).
Antwort bewerten Vielen Dank für Deine Bewertung

Stell es dir arg versimpelt wie eine Reihe von Dominosteinen vor. Zunächst kommt der Induktionsanfang: Du beweist, dass der ERSTE Dominostein umfällt.

Dann beweist du, dass wenn der n. Dominostein umfällt, auch der n+1. umfällt. Dadurch dass also der erste umfällt (nach Induktionsanfang), fällt der zweite um. Da der zweite umfällt, wird der dritte umfallen. Und so weiter, bis zur Unendlichkeit...

... und noch vieeeel weiter.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von kreisfoermig
17.10.2016, 19:38

... und noch vieeeel weiter.

mmm, eben nicht. Für Limesordinalzahlen reich der beweis von AUSSAGE(ξ) → AUSSAGE(ξ+1) nicht aus. Man muss dann schon (∀η<ξ: AUSSAGE(η)) → AUSSAGE(ξ) beweisen für alle Ordinalzahlen ξ, und da versagt die bildliche Metaphor.

0

n+1 ist immer abgedeckt, da du bei einer vollständigen Induktion für alle n größer als deine Startzahl beweist. 

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?