Lineare Algebra: Grundlagen: Vollständige Induktion

Grundidee

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

• 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

Nun wollen wir durch Vollständige Induktion zeigen, dass

$\sum _{k=1}^{n}k={\tfrac {1}{2}}n(n+1)$

Zuerst zeigen wir den Induktionsanfang:

$\sum _{k=1}^{1}k=1={\tfrac {1}{2}}1(1+1)$

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

$\sum _{k=1}^{n+1}k=\sum _{k=1}^{n}k+(n+1){\begin{matrix}\underbrace {=} \\{}^{\rm {I.H.}}\\[-4.5ex]\end{matrix}}{\tfrac {1}{2}}n(n+1)+(n+1)=(n+1)({\tfrac {1}{2}}n+1)={\tfrac {1}{2}}(n+1)(n+2)$

Siehe

• Vollständige Induktion [1]