vollständige Induktion

Die vollständige Induktion ist in der Mathematik eine Methode, um Aussagen wie "Für alle natürlichen Zahlen gilt…" zu beweisen. Sie beruht auf dem 5. Axiom der
->Peano-Axiome und erfolgt in zwei Schritten:
(1) Beweise die Gültigkeit einer Aussage A(k) für einen Anfangswert k=n.
(2) Beweise: Wenn A(k) für ein k gilt, so gilt auch A(k+1).
Nach (1) ist A(n) gültig, nach (2) damit auch A(n+1) und wiederum nach (2) auch A(n+2) usw. Damit ist die Aussage A(k) für alle k ≥ n gültig.
Beispiel: Für die Summe \(S_n\) der natürlichen Zahlen 1 bis n gilt \(S_{n}=frac{1}{2}n(n++1)\).
(1) Für n = 1 ist \(S_{1}=frac{1}{2}cdot 1cdot (1++1)\), die Aussage also gültig.
(2) Induktionsannahme: Es sei \(S_{k}=frac{1}{2}k(k++1)\) gültig. Dann ist
\(S_{k++1}=S_k++k++1=frac{1}{2}k(k++1)++k++1=frac{1}{2}(k++2)(k++1)=\)
          \(=frac{1}{2}(k++1)((k++1)++1)\)
Damit ist die Aussage für alle n ≥ 1 bewiesen.