Vollständige Induktion

Das Induktionsaxiom ermöglicht uns Beweise für natürliche Zahlen wie folgt zu führen. Wir zeigen zuerst, dass die Aussage für $0$ wahr ist (Induktionsanfang). zeigen wir weiter, dass aus der Richtigkeit der Aussage für ein beliebiges $n\in \dom N$ auch die Richtigkeit für $n+1$ folgt (Induktionsschritt), dann muss die Aussage für alle natürlichen Zahlen richtig sein.

Man kann dieses Beweisverfahren auch modifizieren, indem man den Induktionsanfang nach hinten legt, also mit $1$, $2$ oder einer noch größeren Zahl beginnt. Dann gilt die Aussage für alle natürlichen Zahlen mit Ausnahme derjenigen, die kleiner als die für den Induktionsanfang gewählte Zahl sind.

Besonders häufig wird dieses Verfahren angewandt, um Formeln für Partialsummen zu beweisen.

$\sum\limits_{i=0}^n i=\dfrac {n(n+1)} 2$

Induktionsanfang: $\sum\limits_{i=0}^0 i=0=\dfrac {0(0+1)} 2$.

Induktionsschritt:

$\sum\limits_{i=0}^{n+1} i =\sum\limits_{i=0}^n i + (n+1)$ $= \dfrac {n(n+1)} 2+ (n+1)$ $=\dfrac {n(n+1)+2(n+1)} 2$ $=\dfrac {(n+1)(n+2)} 2$ $\qed$