Frage von Xihangg, 37

Vollständige Induktion, verstehe Schlussfolgerung nicht?

Man macht den Induktionsanfang und beweist für das kleinste n. Dann beweist man es für ein k+1... Wieso ist dann die Annahme richtig???

Expertenantwort
von Willy1729, Community-Experte für Mathematik, 16

Hallo,

meist werden über die vollständige Induktion Formeln bewiesen wie die Summe der natürlichen Zahlen 1+2+3+...+n-1+n.

Dafür gibt es die bekannte Summenformel (n/2)*(n+1)

Die Summe der ersten 6 natürlichen Zahlen, also 1+2+3+4+5+6 wäre nach der Formel (6/2)*(6+1)=3*7=21.

Tatsächlich ergibt die Summe der ersten 6 natürlichen Zahlen 21, wie jeder Grundschüler leicht nachrechnen kann.

Um zu beweisen, daß die für beliebige n gilt, weist Du nach, daß Du mit Hilfe der Formel von einem n zum nächsten kommen kannst, daß also

(n/2)*(n+1)+(n+1) dasselbe ergibt, wie wenn Du dieses n+1 gleich in die Formel einsetzt: ((n+1)/2)*(n+1+1)=(n/2)*(n+1)+n+1

Den Induktionsanfang brauchst Du, um zu zeigen, daß die Formel überhaupt funktioniert, denn wenn der Anfang schon falsch ist, hat sich das mit dem Beweis ohnehin erledigt.

(1/2)*(1+1)=1; das ist zweifellos korrekt.

Wenn Du nun zu der Formel (n/2)*(n+1) das nächste Glied, also n+1 addierst, bekommst Du (n/2)*(n+1)+n+1, also
n²/2+n/2+n+1=n²/2+3n/2+1

Dasselbe muß herauskommen, wenn Du, anstatt n+1 zu addieren, n+1 anstatt n in die Formel einsetzt:

[(n+1)/2]*(n+2)=(1/2)*(n+1)*(n+2)=(1/2)*(n²+3n+2)=n²/2+3n/2+1.

Das ist dasselbe Ergebnis, die Formel funktioniert also, den wenn Du mit ihrer Hilfe von einem beliebigen n zum nächsten kommst, hat sie ihren Zweck erfüllt.

Herzliche Grüße,

Willy

Kommentar von Xihangg ,

Aber wir wissen doch gar nicht ob es für irgendein n funktioniert, außer für das kleinste. Bewiesen wäre das doch dann nur für n=2 oder net?

Kommentar von Willy1729 ,

Doch!

Wir wissen, daß es für das erste funktioniert und wir haben bewiesen, daß es für ein beliebiges folgendes Glied funktioniert. Bei der 1 beginnend kannst Du die Kette also endlos fortsetzen.

Antwort
von Naydoult, 14

"Man macht den Induktionsanfang und beweist für das kleinste n."

Das ist korrekt. Es ist wichtig das man es für das kleinste n beweist.

Also man könnte beispielsweise folgendes Schema beim Aufstellen eines Induktionsbeweises benutzen:

1. Behauptung und Voraussetzungen (Was ist zu beweisen? Was benötigen wir eventuell sonst noch dazu?)

2. Induktionsanfang (Für das aller kleinste n zeigen)

3. Induktionsschritt (Für n+1 zeigen)

4. Schluss (Schreiben das der Satz gilt und vielleicht erläutern)

Wir wollen z.B zeigen das n=n ist, für Alle n in lN. Fangen wir also mit der 0 an, dann haben wir 0=0 was eine wahre Aussage ist. Nun beweist Du es für n+1, wenn diese richtig ist, so gilt es für alle n. Denn n+1 für n=0 wäre n=1 und dies ist korrekt. Wir haben aber bereits für n+1 geschlossen das diese auch richtig ist. Also ist n+1 wieder korrekt für n=1 und so weiter...

Expertenantwort
von Ellejolka, Community-Experte für Mathematik, 19

man beweist, dass wenn die Behauptung für k gilt(Annahme), sie dann auch für den Nachfolger k+1 gilt (Induktionsschluss) . Das ist die Beweisführung der vollst. Induktion.

Wenn dich interessiert, warum man so vorgeht, solltest du vielleicht Herleitung "vollst. Induktion" googeln.

Antwort
von Mikkey, 21

Wenn die Aussage für irgendein m > n falsch wäre, müsste sie wegen des bewiesenen Induktionsschritts auch für m-1 falsch sein, ebenso für m-2, m-3 usw. Dann wäre sie auch für n falsch, was aber bereits widerlegt wurde.

Antwort
von Gonti, 17

"Man macht den Induktionsanfang und beweist für das kleinste n."

So ist das nicht korrekt. Ein Beispiel wäre etwa die Ungleichung

n^2\leq 2^n (wobei \leq hier für "kleiner gleich" (Less EQual), oder unschön geschrieben =<) stehen soll.

Dies ist bereits für n=2 richtig. Denn 4=4, aber für n=3 ergibt sich 

9\leq 8, was sicherlich falsch ist. 

Die Aussage ist erst für alle n richtig, die größer gleich 4 sind. Somit wäre der Induktionsanfang als 4 zu wählen, obwohl die Aussage auch für n=2 richtig ist.

"Dann beweist man es für ein k+1"

Inkonsequente Bezeichnung, man zeigt, dass wenn die Aussage für jedes feste, aber beliebige n (mit gegebener Voraussetzung) gilt, dass sie dann auch für n+1 gilt.

"Wieso ist dann die Annahme richtig?"

Welche Annahme? Die Induktionsannahme wird als richtig "angenommen" und im Induktionsschritt verwendet. 
Das die Induktionsannahme korrekt ist, wird mehr oder weniger im Induktionsanfang verifiziert.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten