Induktionsbeweis

Mit Hilfe der vollständigen Induktion lassen sich Aussagen über natürliche Zahlen beweisen, also Aussagen der Form $A(n)$.
Im obigen Beispiel war $A(n)$ die Aussage:

$A(n)$: Es gibt $2^n$ Teilmengen einer $n$-elementigen Menge.

Induktionsbeweise haben immer den gleichen ungefähren Aufbau.

• Induktionsverankerung/Induktionsstart Wir zeigen zunächst die Aussage $A(0)$
• Induktionsannahme/Induktionsvoraussetzung Wir nehmen nun an, dass $A(n)$ für ein $n$ gilt.
• Induktionsschritt/Induktionsschluss $A(n+1)$ wird unter Zuhilfenahme der Gültigkeit von $A(n)$, also der Induktionsannahme, bewiesen.

Links

• DS_vollständiger_foliensatz.pdf