Die vollständige Induktion – Ein mathematisches Prinzip

Die vollständige Induktion ist eine fundamentale Methode in der Mathematik, um Aussagen zu beweisen, die für alle natürlichen Zahlen oder ab einem bestimmten Wert gelten. Sie ähnelt dem Dominoeffekt: Wenn der erste Dominostein fällt (Induktionsanfang) und jeder weitere den nächsten umstößt (Induktionsschritt), dann fallen alle.

Struktur der vollständigen Induktion

• Induktionsanfang (IA): Zeige, dass die Aussage A(n) für den Startwert (z. B. n = 0 oder n = 1) wahr ist.
• Induktionsschritt (IS):
  • Induktionsvoraussetzung (IV): A(k) gilt für ein beliebiges, aber festes k.
  • Induktionsbehauptung (IB): A(k+1) soll unter der Voraussetzung gelten.
  • Beweis: Zeige, dass A(k) ⇒ A(k+1).

Aussageform und Allgemeingültigkeit

Bei A(n) handelt es sich um eine Aussageform, die eine freie Variable enthält. Ziel ist es zu zeigen, dass A(n) für alle n aus der Grundmenge (z. B. ℕ) gilt.

Varianten der Induktion

• Induktionsanfang bei beliebigem Startwert: Die Induktion kann bei n = n₀ beginnen.
• Starke Induktion: Es wird angenommen, dass A(l) für alle m ≤ l < n gilt, um A(n) zu zeigen.

Typische Anwendungen

• Summenformeln: z. B. 1 + 2 + ... + n = n(n+1)/2
• Ungleichungen: z. B. Σ(1/k)
• Teilbarkeitsaussagen: z. B. 8^m - 3^m ist durch 5 teilbar
• Mengenlehre: Eine n-elementige Menge hat 2ⁿ Teilmengen
• Binomischer Lehrsatz: (x + y)ⁿ = Σ (n über k) · x^k · y^n-k
• Anordnungen: n! Möglichkeiten für n Objekte

Hinweis zur Beweispraxis

Ein klar strukturierter Aufbau mit der expliziten Benennung von IA, IV, IB und dem Beweisteil ist essenziell für einen verständlichen Induktionsbeweis.