Rekursion/Induktion/Bemerkung

Eng verwandt mit der vollständigen Induktion ist das Prinzip der rekursiven Definition. Bei dieser möchte man für jede natürliche Zahl ${}n$ einen mathematischen Ausdruck festlegen. Dies macht man, indem man für ${}0$ einen Ausdruck explizit festlegt und beschreibt, wie der Ausdruck für ${}n+1$ aus dem Ausdruck für ${}n$ berechnet werden soll. Letzteres nennt man die Rekursionsvorschrift. Der induktive Aufbau der natürlichen Zahlen stellt dabei sicher, dass durch diese rekursiven Festlegungen für jede natürliche Zahl ein eindeutiger Ausdruck festgelegt wird. Beispielsweise kann man einen Ausdruck ${}F(n)$ durch den Rukursionsanfang

${}F(0):=7\,$

und die Rekursionsvorschrift

${}F(n+1):=F(n)\cdot n-n^{2}+3\,$

festlegen.