Course-Of-Values Induction

Sein $P(n)$ eine Aussage über natürliche Zahlen.

Falls für jedes $n$

gilt und daraus immer $P(n)$ folgt, dann gilt $P$ für jede natürliche Zahl.

Verstärkung des Induktionsziels

Eine Aussage $Q(n)$ ist stärker als $P(n)$, wenn aus $Q(n)$ direkt $P(n)$ folgt.

Wir zeigen also die stärkere Aussage

durch Induktion (Beweis) über $n$.