TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 5
Man beweise mittels vollständiger Induktion
, wobei
{{Beispiel|1= Angabetext }}
oder
{{Beispiel| Angabetext }}
zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)
{{Beispiel|status=solved|1= Angabetext }}
Aufgabe
Induktionsanfang:
Ergibt:
Induktionsvorraussetzung: Es muss gezeigt werden, dass gilt:
(Alle n durch n+1 ersetzt)
Induktionsschluss: (Nachweis der Induktionsvorraussetzung)
Schritt 1
Das Summenzeichen sagt uns, dass wir von 1 bis n+1 addieren sollen. Das ist dasselbe als würden wir zuest 1 bis n addieren und dann noch n+1 dazu geben. Daraus folgt:
(*)
Schritt 2
Aus der Angabe wissen wir (oder eher "vermuten wir"), dass
Deswegen können wir (*) umwandeln zu:
(#)
Schritt 3
Ziel ist es, die Induktionsvoraussetzung zu beweisen. Deswegen müssen wir jetzt den Term (#), der der linken Seite der Induktionsvoraussetzung entspricht, solange umformen, bis er genauso aussieht wie die rechte Seite der Induktionsvoraussetzung.
Kurz gesagt, wir müssen (#) umformen, bis wir als Ergebnis bekommen:
Zur Erinnerung: dieses Ergebnis (über dieser Zeile) ist die linke Seite der Induktionsvoraussetzung umgeformt. Wir setzen nun wieder in die Induktionsvoraussetzung ein und erhalten dadurch: