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

...komplette Frage anzeigen

2 Antworten

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.

Antwort bewerten Vielen Dank für Deine Bewertung
Naydoult 28.09.2016, 18:05

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

0
Tannibi 28.09.2016, 18:08
@Naydoult

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.

0

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.

Antwort bewerten Vielen Dank für Deine Bewertung
Naydoult 28.09.2016, 18:05

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

0
Wechselfreund 28.09.2016, 18:18
@Naydoult

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...

0
Naydoult 28.09.2016, 18:31
@Wechselfreund

Induktionsannahme.

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

0
Schachpapa 28.09.2016, 18:32
@Naydoult

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)

0
Naydoult 28.09.2016, 18:35
@Schachpapa

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.

0
Schachpapa 28.09.2016, 18:44
@Naydoult

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.

0

Was möchtest Du wissen?