Vollständige Induktion

Ein Aussage A(n) für alle $n\in \mathbb{N}$ mit $n\ge n_0$ zeigen wird, dass die aussage für $n_0$ gilt. Dann zeigen wir, dass $A(n)$ für ein beliebiges $n>n_0$ und $n+1$ gilt. Also wenn $A(n)$ wahr ist, dann ist auch $n+1$ wahr.

1. Als erstes muss man den Induktionsanfang (IA) zeigen. Also, dass für $n_0$ die Aussage A(n) stimmt.
2. Im Induktionsschritt (IS) zeigen wir, dass "$A(n)⟹A(n+1)$" wahr ist, also dass wenn $A(n)$ wahr ist auch $A(n+1)$ wahr ist
   1. Induktionsvorraussetzung (IV): Wir nehmen an, dass für $A(n)$ für ein $n\ge n_0$ richtig ist.
   2. Induktionsbehauptung (IB): "Dann gilt auch $A(n+1)$"
   3. Der eigentliche Induktionsschritt, auch Induktionsschluss genannt, zeigt die Induktionsbehauptung unter Benutzung der Induktionsvorraussetzung.