Lineare Algebra: Grundlagen: Vollständige Induktion

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  

 
  • Vollständige Induktion [1]