Vollständige Induktion

Im Erlebnisland Mathematik gibt es eine Reihe von Exponaten, die auf den ersten Blick verblüffen: sogenannte „Beweise ohne Worte“. Dabei handelt es sich um anschauliche Puzzles, die eine allgemeine mathematische Aussage für kleine Fälle so überzeugend darstellen, dass man fast schon von einem Beweis sprechen möchte.

  • Die Summe der ersten n ungeraden Zahlen: Hier bestehen die Teile aus L-förmigen Bausteinen: der erste enthält 1 Kästchen, der zweite 3, der dritte 5, und so weiter. Legt man die Teile nacheinander aneinander, wächst jedes Mal ein Quadrat um eine Kästchenlänge. Für n=4 ergibt sich so ein 4\times 4-Quadrat mit 16 Kästchen – ein augenfälliger Hinweis auf die Formel

        \[ 1+3+5+\dots+(2n-1)=n^2. \]

Abbildung 1: Das Exponat „Beweis ohne Worte: Summe der ersten n ungeraden Zahlen“
  • Die Summe der ersten n Zahlen: In einem anderen Exponat wird die Summe 1+2+3+\dots+n als Puzzle dargestellt. Für n=7 etwa lassen sich die Kästchen in ein Rechteck legen, das 7\cdot 8/2=28 Felder enthält. Damit sieht man sofort, dass die Summe zu einer einfachen Flächenformel führt.
Abbildung 2: Das Exponat „Beweis ohne Worte: Summe der ersten n Zahlen“
  • Die Summe der Quadratzahlen: Auch für 1^2+2^2+3^2+\dots+n^2 gibt es eine geometrische Zerlegung. Hier werden Quadrate verschiedener Größe zu einem größeren Rechteck zusammengesetzt, sodass man eine Vermutung für die allgemeine Formel gewinnt.
Abbildung 3: Das Exponat „Beweis ohne Worte: Summe der Quadratzahlen“

Diese Bilder sind heuristisch sehr überzeugend, aber sie zeigen die Gültigkeit nur für kleine Werte, etwa n=4 oder n=7.

Doch Mathematikerinnen und Mathematiker wollen mehr: Sie möchten sicher sein, dass die Formel für alle natürlichen Zahlen stimmt – und das sind unendlich viele Fälle.

Genau hier hilft das „Beweisprinzip der vollständigen Induktion“.
Es funktioniert wie eine unendliche Leiter:

  1. Induktionsanfang: Man zeigt, dass die erste Stufe (meist n=1) trägt.
  2. Induktionsschritt: Man beweist: Wenn eine beliebige Stufe n hält, dann trägt auch die nächste, n+1.

Sobald beides gelingt, steht fest: Man kann von der ersten Stufe immer weiter hinaufklettern, also gilt die Aussage für alle natürlichen Zahlen.

Und nun … die Mathematik

Wir wenden dieses Prinzip auf drei schöne Beispiele an, die auch im Erlebnisland Mathematik durch Exponate anschaulich dargestellt sind.

 

Die Summe der ungeraden Zahlen

Als erstes zeigen wir einen Beweis durch vollständige Induktion über die Summe der ersten n ungeraden Zahlen:

Behauptung: Es soll gezeigt werden, dass

    \[1+3+5+\dots+(2n-1)=n^2\]

Induktionsanfang: Für n=1 gilt: 1=1^2.

Induktionsschritt: Angenommen, die Formel gilt für ein n \in \mathbb{n}, also

    \[\sum_{i=1}^n (2i-1)=n^2.\]

Dann gilt für n+1:

    \[\sum_{i=1}^{n+1} (2i-1) = n^2 + (2(n+1)-1) = n^2 + 2n +1 = (n+1)^2.\]

Damit ist die Behauptung bewiesen.

 

Die Summe der ersten n Zahlen

Wir widmen uns nun einer ähnlichen Aussage, diesmal aber nicht über die Summe der ersten n ungeraden Zahlen, sondern der ersten n Zahlen:

Zu dieser Aufgabe gibt es eine Anekdote aus den Schulzeiten von Carl Friedrich Gauß (1777–1855). Im „Spektrum der Wissenschaft Spezial“, 2/2009, wird berichtet: „Über den neunjährigen Gauß wird erzählt, dass er in kürzester Zeit mit einer Rechenaufgabe fertig ist, die sein Lehrer Büttner der Klasse aufgetragen hat: Das Summieren der ersten 100 Zahlen. Seine Überlegung ist: Von „außen“ nach „innen“ vorzugehen. Dazu fasst er jeweils die kleinste und die größte Zahl zu einer Summe zusammen: 1+100, 2+99, 3+98, …, 50+51. Das ergibt 50-mal die Summe 101, also 5050. Lehrer Büttner spürt, dass er diesem Jungen nicht wirklich etwas beibringen kann und schenkt ihm ein Schulbuch über Arithmetik, das sich dieser selbstständig erarbeitet.“ Das ist nicht die gleiche Herangehensweise wie sie im entsprechenden Exponat im ERLEBNISLAND MATHEMATIK gezeigt wird, aber auch diese Geschichte macht deutlich, dass man mit systematischem Überlegen schneller und weiter kommt als mit einfachem „Drauflosrechnen“. Das Ergebnis ist aber das gleiche: Auch Gauß erhält (für den Fall n= 100):

    \[50\cdot 101=\frac{100\cdot 101}{2}=\frac{n(n+1)}{2}.\]

Der Induktionsbeweis geht wie folgt:

Behauptung: Es soll gezeigt werden, dass

    \[1+2+3+\dots+n=\frac{n(n+1)}{2}\]

Induktionsanfang: Für n=1 gilt: 1=\tfrac{1\cdot 2}{2}.

Induktionsschritt: Angenommen, die Formel gilt für n \in \mathbb{N}, also

    \[\sum_{i=1}^n i = \frac{n(n+1)}{2}.\]

Dann gilt für n+1:

    \[\sum_{i=1}^{n+1} i = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}.\]

Auch hier bestätigt die Induktion die Vermutung.

 

Die Summe der Quadratzahlen

Wir schließen mit einem letzten Induktionsbeweis über die Summe der ersten n Quadratzahlen:

Behauptung: Es soll gezeigt werden, dass

    \[1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}\]

Induktionsanfang: Für n=1 gilt: 1=\tfrac{1\cdot 2\cdot 3}{6}=1.

Induktionsschritt: Angenommen, die Formel gilt für n, also

    \[\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}.\]

Dann gilt für n+1:

    \[\sum_{i=1}^{n+1} i^2 = \frac{n(n+1)(2n+1)}{6}+(n+1)^2 = \frac{(n+1)(n+2)(2n+3)}{6}.\]

Damit ist auch diese Formel bewiesen.

 

Fazit

Die vollständige Induktion wirkt auf den ersten Blick wie ein kleiner Trick, ist aber eines der mächtigsten Werkzeuge der Mathematik. Ob bei einfachen Zahlenfolgen oder bei hochkomplexen Strukturen, sie zeigt, wie man aus dem sicheren Fundament eines einzelnen Falles unendliche Weiten erklimmen kann.

Literatur

[1] https://de.wikipedia.org/wiki/Vollständige_Induktion.

[2] https://de.wikipedia.org/wiki/Gaußsche_Summenformel.