Zum Inhalt springen

Lineare Algebra: Grundlagen: Vollständige Induktion

Aus Wikibooks

Grundidee

[Bearbeiten]

Eine mathematische Aussage A(n) für alle natürlichen Zahlen n soll bewiesen werden.

Dazu beweist man direkt, dass A(1) gilt (Induktionsanfang) und vollzieht dann den Induktionsschritt. Ausgehend von der Induktionsvoraussetzung -- die Aussage gelte für ein beliebiges aber festes n -- beweist man, dass dann auch A(n+1) gelten muss.

Damit ist A(n) für alle natürlichen Zahlen n bewiesen.

Varianten

[Bearbeiten]
  • Aussagen über Teilmengen der natürlichen Zahlen (z.B. "Für alle geraden n gilt: ...") können bewiesen werden, indem der Induktionsanfang und -schritt angepasst wird (z.B. A(2) direkt, n -> n+2)
  • Manchmal (z.B. Graphentheorie) wird im Induktionsschritt das Problem in kleinere Teilprobleme zerlegt und unter der Induktionsvoraussetzung gefolgert, dass die Aussage über die Teilprobleme wahr ist. Der Schritt wird also nicht notwendigerweise von n nach n+1 sondern von z.T. deutlich kleineren Indizes geführt.

Beispiel

[Bearbeiten]

Nun wollen wir durch Vollständige Induktion zeigen, dass

Zuerst zeigen wir den Induktionsanfang:

Als nächstes nehmen wir an, dass die Behauptung für ein bestimmte gelte.
Jetzt kommt der Induktionsschritt von

Siehe

[Bearbeiten]
  • Vollständige Induktion [1]