Vollständige Induktion, verstehe Schlussfolgerung nicht?

...komplette Frage anzeigen

5 Antworten

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

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Xihangg
06.09.2016, 18:41

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?

0

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

Antwort bewerten Vielen Dank für Deine Bewertung

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 bewerten Vielen Dank für Deine Bewertung

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 bewerten Vielen Dank für Deine Bewertung

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

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?