Vollständige Induktion

Die vollständige Induktion ist ein Beweisverfahren für Aussagen, die für alle natürlichen Zahlen n gelten sollen. Ein Beispiel ist die Formel 1 + 2 + … + n = n(n + 1)/2. Du kannst nicht unendlich viele Zahlen einzeln nachprüfen. Die Induktion umgeht das mit nur zwei Schritten: Du zeigst, dass die Aussage für die erste Zahl stimmt (Induktionsanfang), und dass sie sich von jeder Zahl k auf die nächste Zahl k + 1 überträgt (Induktionsschritt).

Hier lernst du das Prinzip am Dominomodell, den genauen Aufbau, fünf Beispiele (Summen, Ungleichung, Teilbarkeit, Folgen, starke Induktion), die typischen Fehler samt Pferde-Paradox, Übungen und die Geschichte. Einen Überblick über andere Beweisarten gibt die Seite Beweisverfahren, die Wenn-dann-Aussagen erklärt die Aussagenlogik.

Das Dominoprinzip

Stell dir unendlich viele Dominosteine vor, die in einer Reihe stehen und mit 1, 2, 3, … nummeriert sind. Dass alle umfallen, folgt aus zwei Tatsachen. Erstens fällt der erste Stein. Zweitens reißt jeder Stein, der fällt, den nächsten mit, denn die Abstände sind so gewählt, dass Stein k den Stein k + 1 trifft. Mehr brauchst du nicht: Stein 1 stößt Stein 2 um, Stein 2 stößt Stein 3 um, und so geht es endlos weiter.

Wichtig: Im zweiten Schritt behauptest du nicht, dass $A(k)$ wahr ist. Du zeigst nur die Wenn-dann-Aussage $A(k)\Rightarrow A(k+1)$. Erst das Zusammenspiel mit dem Anfang macht aus „wenn“ ein „ist“.

Aufbau eines Induktionsbeweises

1. Behauptung: Schreibe die Aussage $A(n)$ genau hin und sage, für welche $n$ sie gelten soll.
2. Induktionsanfang: Zeige $A(n_0)$ durch Einsetzen.
3. Induktionsvoraussetzung: Notiere: „Die Aussage $A(k)$ gelte für ein beliebiges, festes $k\ge n_0$.“
4. Induktionsschritt: Schreibe $A(k+1)$ auf und forme es so um, dass $A(k)$ darin vorkommt. Wende dann die Voraussetzung an und rechne zu Ende.
5. Schluss: „Nach dem Prinzip der vollständigen Induktion gilt $A(n)$ für alle $n\ge n_0$.“

Der Kunstgriff liegt in Schritt 4. Bei einer Summe spaltest du den letzten Summanden ab, bei einer Potenz klammerst du einen Faktor aus, bei einer Teilbarkeit schreibst du die Zahl als Summe aus einem Teil mit der Voraussetzung und einem Rest.

Beispiel 1: Die Summenformel von Gauß

Die Summe der ersten n Zahlen kennst du von Gauß’ Paartrick. Mit dem Summenzeichen ∑ (gesprochen „Summe“) schreibst du sie kurz. Du willst beweisen:

Die Induktion beweist die Formel, sie verrät aber nicht, wie man darauf kommt. Dafür braucht man eine Idee wie das Paarbilden von Gauß oder ein Muster, das man vorher durch Probieren gefunden hat.

Beispiel 2: Die Bernoullische Ungleichung

Auch Ungleichungen lassen sich per Induktion beweisen. Die Bernoullische Ungleichung ist nach Jakob Bernoulli benannt, der sie 1689 in einer Arbeit über unendliche Reihen verwendete. Sie sagt: Für jede reelle Zahl $x\ge -1$ und jede natürliche Zahl $n\ge 1$ gilt

Beachte, wo die Voraussetzung $x\ge -1$ gebraucht wurde: beim Multiplizieren mit $1+x$. Wäre $1+x$ negativ, würde sich das Ungleichheitszeichen umdrehen.

Eine Anwendung steckt im Zinseszins: Bei 1 % Zinsen im Jahr gilt ${\mathrm{1,01}}^{100}\ge 1+100·\mathrm{0,01}=2$. Das Kapital hat sich nach 100 Jahren also mindestens verdoppelt. Tatsächlich wächst es auf das 2,70-Fache.

Beispiel 3: Teilbarkeit

Behauptung: Für alle $n\ge 1$ ist $n^3+2n$ durch 3 teilbar. Wenn a durch 3 teilbar ist, schreibt man $3|a$.

Beispiel 4: Fibonacci-Zahlen

Die Induktion passt gut zu rekursiv definierten Folgen. Die Fibonacci-Zahlen (nach Leonardo von Pisa) sind durch $f_1=f_2=1$ und $f_{n+2}=f_{n+1}+f_n$ festgelegt: 1, 1, 2, 3, 5, 8, 13, … Behauptung: Die Summe der ersten $n$ Fibonacci-Zahlen ist $f_{n+2}-1$. Zum Beispiel ist $1+1+2+3+5=12=13-1$.

Starke Induktion

Manchmal reicht die Annahme für $k$ allein nicht aus. Bei der starken Induktion setzt du in der Voraussetzung voraus, dass $A(m)$ für alle $m$ mit $n_0\le m\le k$ gilt, und zeigst daraus $A(k+1)$. Sie ist gleichwertig zur gewöhnlichen Induktion, oft aber bequemer.

Dass die Zerlegung auch eindeutig ist, zeigt man anders. Mehr zur Primfaktorzerlegung steht auf der Seite über Primzahlen.

Wann hilft die Induktion?

Die Induktion passt, wenn du eine Aussage über alle natürlichen Zahlen beweisen willst und sich $A(k+1)$ aus $A(k)$ ergibt. Das ist typisch bei Summen, Produkten, Teilbarkeit, Ungleichungen und rekursiven Folgen. Bei Aussagen über reelle Zahlen hilft sie nicht. In der Informatik beweist man mit ihr, dass rekursive Programme richtig arbeiten: Der Induktionsanfang ist der Abbruchfall der Rekursion, der Induktionsschritt der rekursive Aufruf.

Typische Fehler

Ohne Anfang: eine falsche Formel

Betrachte die Behauptung $1+2+\dots +n=\frac{n(n+1)}{2}+5$. Mit der Voraussetzung rechnest du im Schritt: $\frac{k(k+1)}{2}+5+(k+1)=\frac{(k+1)(k+2)}{2}+5$. Der Induktionsschritt gelingt also. Trotzdem ist die Aussage falsch, schon für $n=1$: Links steht 1, rechts 6. Der Schritt allein reicht nie, der Anfang gehört dazu.

Das Pferde-Paradox

Das Paradox geht auf Überlegungen von George Pólya (1954) zurück. Die Pferde-Fassung stammt aus einem Aufsatz von Joel E. Cohen von 1961.

Übungen

Geschichte: von Maurolico bis Peano

Induktionsartige Schlüsse finden sich schon früh. Al-Karadschi nutzte um das Jahr 1000 beim Zahlendreieck eine frühe Form. Als erster ausdrücklicher Induktionsbeweis gilt lange der des Italieners Francesco Maurolico (1494–1575). In seinem Buch Arithmeticorum libri duo (verfasst 1557, gedruckt 1575) zeigte er, dass die Summe der ersten n ungeraden Zahlen gleich n² ist. Das allgemeine Verfahren beschrieb er noch nicht.

Blaise Pascal formulierte 1654 in seinem Traité du triangle arithmétique Induktionsanfang und Induktionsschritt ausdrücklich. Jakob Bernoulli setzte das Verfahren in seinen Arbeiten ab den 1680er-Jahren breit ein. Das Wort „Induktion“ für diese Beweisart verwendete 1838 Augustus De Morgan, und Richard Dedekind prägte 1888 in Was sind und was sollen die Zahlen? den Begriff „vollständige Induktion“. Ein Jahr später machte Giuseppe Peano das Induktionsprinzip zum Axiom der natürlichen Zahlen: Gilt eine Eigenschaft für 0 und vererbt sie sich von jeder Zahl auf ihren Nachfolger, so gilt sie für alle natürlichen Zahlen.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Vollständige Induktion
• MacTutor History of Mathematics: Francesco Maurolico (englisch)
• Richard Dedekind: Was sind und was sollen die Zahlen?, Vieweg, Braunschweig 1888.
• Giuseppe Peano: Arithmetices principia, nova methodo exposita, Bocca, Turin 1889.
• George Pólya: Induction and Analogy in Mathematics, Princeton University Press, Princeton 1954.