Frage von Naydoult, 53

Wieso darf die Induktionsannahme als wahr angenommen und so benutzt werden?

Das Prinzip der vollständigen Induktion habe ich ja verstanden, aber wieso darf man beim beweisen die Induktionsannahme verwenden? Wir wissen doch gar nicht ob sie korrekt ist, klar es ist eine Annahme. Aber wenn wir sie wo einsetzen könnten wir doch alles mögliche damit machen, vorausgesetzt sie gilt für die 0 oder 1.

Antwort
von Tannibi, 30

Du musst bei der VE zwei Dinge beweisen:

- Der Satz gilt für einen bestimmten Wert
- Wenn er für einen irgendeinen Wert gilt, dann
  gilt er auch für den Wert plus 1.

Das Erste "beweist" du durch ausrechnen, mit einem
gegebenen Wert geht das ja immer. Das zweite
musst du tatsächlich beweisen. Anschließend
weißt du: Wenn der Satz für 1 gilt, gilt er auch für 2.
Und wenn er für 2 gilt, gilt er auch für 3 usw.

Kommentar von Naydoult ,

Das ist mir doch klar. Aber wieso darf die IA beim Beweis eingesetzt werden?

Kommentar von Tannibi ,

Weil es eigentlich keine Annahme ist. Du kannst es einfach
überprüfen, indem du den Startwert in den Satz einsetzt
und überprüfst, ob es stimmt.

Antwort
von Schachpapa, 30

Bei der vollst. Induktion beweist du aus der Annahme den nächsten Schritt.

Es gehört aber unbedingt der Induktionsanfang dazu. Wenn du den nicht findest, ist dein "Beweis" kein Beweis.

Kommentar von Naydoult ,

Das ist mir doch klar. Aber wieso darf die IA beim Beweis eingesetzt werden?

Kommentar von Wechselfreund ,

Was verstehst du unter IA? Es muss bewiesen werden, dass es für ein bestimmtes n gilt, dann wird gezeigt, gilt es für n, dann folgt daraus, dass es für n+1gilt. Und dass es für ein n gilt, hast du ja schon bewiesen...

Kommentar von Naydoult ,

Induktionsannahme.

Das es für n gilt wurde aber nur für n_0 gezeigt.

Kommentar von Schachpapa ,

Du zeigst formal, dass der zu beweisende Satz für n+1 gilt, wenn er für n gilt. Wenn du dann irgendein n findest, für das der Satz gilt, gilt er damit auch für n+1 und damit für n+2 usw.

Beispiel:

Satz: Für n>0 ist 2^n - 1 durch 2 teilbar.

Induktionsschritt:
2^(n+1) - 1 = 2^n * 2 - 1 = 2^n + 2^n - 1

2^n = 2 * 2 * 2 ... ist offensichtlich durch 2 teilbar.
Wenn (nach Annahme) 2^n-1 durch 2 teilbar ist, so auch 2^(n+1)-1, denn es ist die Summe zweier durch 2 teilbaren Zahlen.

Der Induktionsschritt ist formal richtig. Es gibt aber keinen Anfang. Deshalb taugt der ganze Beweis nicht. Leider ist das nicht immer so offensichtlich wie in diesem Beispiel.

(Ich hatte mal ein besseres Beispiel, das nicht ganz so offensichtlich war. Leider finde ich es nicht mehr)

Kommentar von Naydoult ,

Ich habe aber nur gezeigt das es für n+1 gilt wenn es für n gilt. Nicht das wenn es für n+1 für n+1+1 gilt. Das ist doch auch keine Konsequenz, da es doch für 1 oder 2 theoretisch falsch sein könnte.

Kommentar von Schachpapa ,

n ist eine beliebige ganze Zahl.

Wenn du formal zeigst, dass du von jedem beliebigen n auf n+1 schließen kannst, und es für n=5000 gilt, dann gilt es auch für n+1=5001. Und wenn es für n=5001 gilt, dann auch für n+1=5002 usw. Also ab dem Induktionsanfang für  alle größeren n.

Normalerweise fängt man aber nicht erst bei 5000 an, sondern meist bei n=1.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten