Induktion
Die Induktion ist ein mathematisches Verfahren, um Aussagen über den natürlichen Zahlen zu beweisen.
Einsatz zum Beweis der Richtigkeit rekursiver und iterativer Algorithmen.
Sei S(n) eine beliebige Aussage über eine ganze Zahl n. Der Beweis, dass S(n) für alle Zahlen n > k richtig ist geht in folgenden Schritten vonstatten:
- Induktionsanfang: Beweise die Aussage für ein k > 0 (meist k=0).
- Induktionsschritt: Beweise, dass unter der vorausgesetzten Gültigkeit von S(n) für alle n > k auch S(n + 1) richtig ist.