Lineare Algebra: Grundlagen: Vollständige Induktion

GrundideeBearbeiten

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.

VariantenBearbeiten

  • 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.

BeispielBearbeiten

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  

 

SieheBearbeiten

  • Vollständige Induktion [1]