Vollständige Induktion

02.03.2014, 13:24

Filius Bonacci

Vollständige Induktion

Meine Frage:
Nun, ich bin noch Schüler eines Gymnasiums und finde die Mathematik sehr interessant.

Ich habe mich viel mit Beweisverfahren beschäftigt, allerdings verstehe ich nicht das Prinzip der vollständigen Induktion.

Ich habe bereits viele Tutorials etc. angeschaut, aber dennoch habe ich eine Frage:

Meine Ideen:
Den Induktionsanfang verstehe ich. Und das Aufstellen der allgemeinen Gleichung auch.
Aber warum setzt man danach (n+1) ein? Und warum ist das danach überhaupt bewiesen?
Ich verstehe die Logik darin einfach gar nicht.....

Kann mir eventuell jemand helfen?

Dankeschön

02.03.2014, 13:31

tigerbine

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Ich verstehe es einfach nicht
[WS] Vollständige Induktion

Die Idee besteht aus 2 Teilen.

* Zeige, dass die Behauptung für einen Startwert gilt, z.B. n=1.

* Zeige, dass WENN sie für n gilt, sie auch für n+1 gilt.

Zusammen folgt daraus:

Gütig für n=1, also auch für n+1 =2, also auch für 2+1=3 usw.

02.03.2014, 20:17

Filius Bonacci

Auf diesen Beitrag antworten »

Danke;

aber irgendwie verstehe ich immer noch nicht den Sinn des Ganzen traurig

Kann man mir das evntuell nochmal ausführlich erklären?

02.03.2014, 20:47

Anxiös

Auf diesen Beitrag antworten »

Stelle dir eine irre lange Reihe Dominosteine vor, die mit $\begin{eqnarray*} 1, 2, 3, \dots \end{eqnarray*}$ beschriftet sind. Fällt der erste Stein (sprich: ist der Induktionsanfang erfüllt), dann können wir weiter sehen.

Jetzt geht es über zur Induktionsvoraussetzung: Du nimmst an (du weißt es nicht, du vermutest einfach), dass der $\begin{eqnarray*} n \end{eqnarray*}$ -te Dominostein fällt.
$\begin{eqnarray*} n \end{eqnarray*}$ kann jetzt der $\begin{eqnarray*} 3. \end{eqnarray*}$ Stein, der $\begin{eqnarray*} 7641. \end{eqnarray*}$ oder der $\begin{eqnarray*} 1. \end{eqnarray*}$ Stein sein. Das wird gleich entscheidend.

Wenn du jetzt zeigen kannst, dass der $\begin{eqnarray*} n \end{eqnarray*}$ nachfolgende Stein $\begin{eqnarray*} n+1 \end{eqnarray*}$ fällt, dann weißt du, dass alle Dominosteine fallen werden (der Induktionsschritt ist erfüllt), DENN was weißt du jetzt? Du weißt der $\begin{eqnarray*} 1. \end{eqnarray*}$ Stein fällt und du weißt, dass jeglicher Stein $\begin{eqnarray*} n \end{eqnarray*}$ den nacholgenden Stein $\begin{eqnarray*} n+1 \end{eqnarray*}$ umschmeißen wird (jetzt noch ohne zu wissen, dass $\begin{eqnarray*} n \end{eqnarray*}$ überhaupt fällt).

ABER: Stein $\begin{eqnarray*} n=1 \end{eqnarray*}$ fällt (hast du gezeigt) und der Nachfolger $\begin{eqnarray*} n+1=1+1=2 \end{eqnarray*}$ fällt damit auch (hast du gezeigt).

Gut: $\begin{eqnarray*} n=2 \end{eqnarray*}$ fällt also, und damit auch der Nachfolger $\begin{eqnarray*} n+1=2+1=3 \end{eqnarray*}$ .
Gut: $\begin{eqnarray*} n=3 \end{eqnarray*}$ fällt also, und damit auch der Nachfolger $\begin{eqnarray*} n+1=3+1=4 \end{eqnarray*}$
Gut: $\begin{eqnarray*} n=4 \end{eqnarray*}$ fällt also, und damit auch der Nachfolger $\begin{eqnarray*} n+1=3+1=5 \end{eqnarray*}$

usw.
usw.
usw.

02.03.2014, 21:10

Leopold

Auf diesen Beitrag antworten »

Induktion bedeutet in der Wissenschaft, aus zahlreichen typischen Einzelbeispielen auf eine allgemeine Regel zu schließen.

Beispiel: Ein Biologe beobachtet Schwäne. Der erste ist weiß, der zweite ist weiß, der dritte ist weiß, und so weiter. Nachdem er 153 Schwäne beobachtet hat und alle weiß waren, stellt er ein Gesetz auf: Jeder Schwan ist weiß.

In der Mathematik ist Induktion problematisch. Das zeigt das folgende Beispiel: Wir beobachten alle natürlichen Zahlen der Form $\begin{eqnarray*} n^2 - n + 41 \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ ganz. Die ersten sind $\begin{eqnarray*} 41,43,47,53,61,71 \end{eqnarray*}$ . Alle diese Zahlen sind Primzahlen. Wir untersuchen die nächsten: $\begin{eqnarray*} 83,97,113,131 \end{eqnarray*}$ . Wieder lauter Primzahlen. Machen wir es wie der Biologe: Alle natürlichen Zahlen der Form $\begin{eqnarray*} n^2-n+41 \end{eqnarray*}$ sind Primzahlen.
Nur ist das leider falsch. Setzt man nämlich $\begin{eqnarray*} n=41 \end{eqnarray*}$ ein: $\begin{eqnarray*} 41^2 - 41 + 41 = 41^2 \end{eqnarray*}$ , so sieht man: Das ist keine Primzahl!

In der Mathematik ist daher Induktion als Beweisverfahren unzulässig. Induktion ist nur zulässig, um eine Vermutung über einen Gegenstand zu erhalten.

Die Mathematik kennt allerdings die vollständige Induktion als Beweisverfahren. Im Unterschied zur gewöhnlichen Induktion ist das jedoch keine Aneinanderreihung von Einzelbeispielen, seien es auch noch so viele. Vielmehr muß man beim sogenannten Induktionsschritt beweisen(!): WENN DIE BEHAUPTUNG FÜR EIN GEWISSES $\begin{eqnarray*} n \end{eqnarray*}$ GILT, DANN GILT SIE AUCH FÜR DEN NACHFOLGER JENES $\begin{eqnarray*} n \end{eqnarray*}$ . Wenn man nun diesen Induktionsschritt bewiesen (!) hat, dann muß man nur noch ein $\begin{eqnarray*} n_0 \end{eqnarray*}$ finden, um die Kette anzustoßen. Wenn man solch ein $\begin{eqnarray*} n_0 \end{eqnarray*}$ findet, kann man speziell dieses als das $\begin{eqnarray*} n \end{eqnarray*}$ aus dem Induktionsschritt nehmen, und man folgert: die Behauptung gilt auch für $\begin{eqnarray*} n_0+1 \end{eqnarray*}$ . Dann kann man dieses $\begin{eqnarray*} n_0+1 \end{eqnarray*}$ als das $\begin{eqnarray*} n \end{eqnarray*}$ aus dem Induktionsschritt nehmen, und man folgert: die Behauptung gilt auch für $\begin{eqnarray*} n_0+2 \end{eqnarray*}$ . Und so setzt sich das fort. Anxiös hat das in das bekannte Bild mit den Dominosteinen gekleidet.

02.03.2014, 21:24

Anxiös

Auf diesen Beitrag antworten »

@Leopold:

Schön erklärt smile

04.03.2014, 18:27

Filius Bonacci

Auf diesen Beitrag antworten »

Hey
Vielen Dank smile

Tut mir Leid, dass ich meine Frage so unverständlich formuliert habe. Also das Prinzip habe ich verstanden. Aber ich verstehe nicht den Induktionsschritt: Wie kann man denn beweisen,dass das n auch für n+1 gilt?
Ich habe mir schon im Internet was über die Gaußsche Summenformel und so angeschaut, aber ich verstehe einfach nicht, wie bzw. wieso man das für den Nachfolger beweisen konnte....

verwirrt

04.03.2014, 18:28

tigerbine

Auf diesen Beitrag antworten »

Man nimmt an, dass die Behauptung für n richtig ist.

Damit zeigt man, dass die Behauptung auch für n+1 richtig ist.

Sollen wir das an einem Beispiel zusammen machen?

05.03.2014, 14:19

un1x

Auf diesen Beitrag antworten »

Ein Beispiel. Du willst beweisen, dass $\begin{eqnarray*} n^2+n \end{eqnarray*}$ immer gerade ist für $\begin{eqnarray*} n \in \mathbb{N}_0 \end{eqnarray*}$

Damit ich dies per vollständiger Induktion beweisen kann, muss ich dies erst mit dem ersten Element prüfuen. Das erste Element von $\begin{eqnarray*} \mathbb{N}_0 \end{eqnarray*}$ ist 0. Jetzt setze ich n=0 und schaue ob das stimmt:

$\begin{eqnarray*} 0^2+0 = 0 \end{eqnarray*}$ und 0 ist gerade. Somit haben wir den ersten Schritt gemacht. Jetzt müssen wir schauen, ob dies auch für n+1 stimmt.

Um die Formel etwas klarer hinzuschreiben, schreibe ich anstelle "gerade" $\begin{eqnarray*} 2k \end{eqnarray*}$ für ein geeignetes $\begin{eqnarray*} k \in \mathbb{N}_0 \end{eqnarray*}$ somit

$\begin{eqnarray*} {\color{red}n^2+n} = 2k \end{eqnarray*}$

Die Induktionsanahme ist dass es für n+1 gilt. Somit:

IA: $\begin{eqnarray*} (n+1)^2+(n+1) = {\color{blue}2r}, r \in \mathbb{N}_0 \end{eqnarray*}$

Um zu Beweisen, dass dies stimmt benutze ich einfach mal den zu beweisenden Teil auf der rechten Seite und passe sie so an, dass beide Seiten das gleiche aussagen

$\begin{eqnarray*} (n+1)^2+(n+1) = ({\color{red}n^2+n})+2n+2 \end{eqnarray*}$

Jetzt benutze die Induktionsannahme auf der rechten Seite und ersetze den zu beweisenden Teil $\begin{eqnarray*} n^2+n \end{eqnarray*}$

$\begin{eqnarray*} (n+1)^2+(n+1) \mathop = \limits^{IA} {\color{blue}2r} + 2n +2 \end{eqnarray*}$
$\begin{eqnarray*} (n+1)^2+(n+1) = 2\underbrace{(r + n +1)}_{k \in \mathbb{N}_0} \end{eqnarray*}$

Somit ist bewiesen, dass es auch für $\begin{eqnarray*} n+1 \end{eqnarray*}$ zutrifft.

05.03.2014, 14:26

tigerbine

Auf diesen Beitrag antworten »

Es widerspricht unserer Netiquette sich einfach in einen laufenden Thread zu hängen. Danke für's zukünftige Beachten. Augenzwinkern

05.03.2014, 14:35

un1x

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Es widerspricht unserer Netiquette sich einfach in einen laufenden Thread zu hängen. Danke für's zukünftige Beachten. Augenzwinkern

Ups wusste ich nicht. Sorry. Kannst gerne wieder löschen.

05.03.2014, 14:45

tigerbine

Auf diesen Beitrag antworten »

Nein, Arbeit löschen wir nicht so schnell. Wollte dir nur "Bescheid" geben. Wink

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen