Vollständige Induktion

Vollständige Induktion oder der „Schluss von n auf n + 1“ ist eine mathematische Beweismethode, die üblicherweise eine Aussage für alle natürlichen Zahlen beweist (verallgemeinert). Sie funktioniert aber auch für allgemeinere Fälle (siehe unten).

Begriff

Der Name dieses Beweisverfahrens leitet sich ab von lat. inductio (= Herein- oder Hinaufführung, im Kontrast zu deductio Herabführung). Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie kein induktives, sondern ein deduktives Prinzip.

Historisches

Die vollständige Induktion findet sich erstmals 1654 bei Blaise Pascal und 1659 bei Pierre de Fermat. Bis zum Jahr 1879 wurde sie jedoch nur für arithmetische Probleme benutzt. Erst als Gottlob Frege damit die Klasse der natürlichen Zahlen definierte, wurde sie zu einem allgemein gültigen Beweisverfahren in der Mathematik.

Übersicht

Vereinfacht gesprochen geht es um folgende Argumentation: Lässt sich die bestimmte Behauptung über natürliche Zahlen für eine gewisse Anfangszahl begründen (Induktionsanfang oder seltener auch Induktionsverankerung) und lässt sich außerdem zeigen, dass aus ihrer Gültigkeit für eine beliebige Zahl $n$ (Induktionsannahme oder Induktionsvoraussetzung) ihre Gültigkeit für die nächste Zahl $n+1$ folgt (Induktionsschluss oder Induktionsschritt), so gilt diese Behauptung für alle auf die Anfangszahl folgenden natürlichen Zahlen. Die Induktion kann also in folgende Stadien unterteilt werden:

1. Induktionsanfang,
2. Induktionsannahme,
3. Induktionsschluss.

Definition

Das Beweisverfahren der vollständigen Induktion beruht auf dem 5. Peano-Axiom für die natürlichen Zahlen $\mathbb {N}$, dem Induktionsaxiom. Dieses besagt:

Ist $K$ eine Teilmenge von $\mathbb {N}$ mit den Eigenschaften, dass 0 (bzw. 1) in $K$ liegt und dass mit jedem Element $k$ von $K$ auch sein Nachfolger $k+1$ in $K$ liegt, dann ist $K$ gleich $\mathbb {N}$.

(Ob man bei 0 oder 1 beginnt, hängt davon ab, ob 0 als Element von $\mathbb {N}$ gezählt wird. Je nach Zweckmäßigkeit ist dies unterschiedlich definiert.)

Um zu beweisen, dass eine bestimmte logische Formel $p(n)$ für jede beliebige natürliche Zahl $n$ gilt, setzt man $K$ als die Menge aller natürlichen Zahlen $k$, für die die Aussage $p(k)$ gilt und wendet anschließend das Induktionsverfahren auf diese Menge an. Somit zeigt man, dass die Aussage $p(1)$ wahr ist und damit das Element 1 in $K$ liegt und dass für jede Aussage $p(k)$ auch die Aussage $p(k+1)$ stimmt, sodass auch $k$ und $k+1$ in der Menge $K$ liegen. Nach dem Induktionsaxiom gilt deshalb $K=\mathbb {N}$, und die Aussage $p(n)$ besitzt für alle natürlichen Zahlen $n\geq 1$ Gültigkeit.

Motivation

Es wird vermutet, dass eine Aussage für alle natürlichen Zahlen gilt. Bei der gegebenen Problemstellung ist es allerdings noch nicht gelungen, einen für alle natürlichen Zahlen gültigen Beweis für die Aussage anzugeben. Da die Menge der natürlichen Zahlen unendlich ist, ist es ebenso nicht möglich, die Richtigkeit der Aussage für jede Zahl einzeln zu beweisen. Durch die Methode der vollständigen Induktion kann aber trotzdem gezeigt werden, ob die Aussage für die gesamte Menge richtig ist.

Beispiel

Zu beweisen ist, dass $1+2+\cdots +n={\frac {n(n+1)}{2}}$ gilt.

Für einzelne Zahlen ist die Formel leicht nachzurechnen:

• Für $n=1$:

  $1={\frac {1(1+1)}{2}}$

• Für $n=2$:

  $1+2=3={\frac {2(2+1)}{2}}$

• und so weiter …

Für den folgenden Beweis reicht bereits der Fall n = 1. Auf der Suche nach einer allgemein gültigen Aussage wird man die Behauptung konsequenterweise für viele andere $n$ überprüfen.

Die Idee

Ist bekannt,

• dass eine bestimmte von $n$ abhängige Aussage für $n=1$ gilt und
• dass für jede beliebige natürliche Zahl $k$ aus der Gültigkeit der Aussage für $n=k$ auch die Gültigkeit für $n=k+1$ folgt,

dann folgt nach dem Induktionsaxiom, dass diese Aussage für alle $n$ gilt.

Auf den ersten Blick scheint das Problem nur anders formuliert worden zu sein, indem die nächste Zahl einfach als die vorhergehende plus 1 bezeichnet wurde. Immer noch sind es unendlich viele Zahlen, doch durch den allgemeinen Ausdruck $n=k+1$ kann davon ausgegangen werden, dass die Aussage für $n=1$ bis $n=k$ gilt. Selbst die Formel, die man zu beweisen sucht, kann im Beweis als Voraussetzung für Zahlen unterhalb der aktuellen Zahl (das bedeutet unterhalb von $k+1$) verwendet werden.

Angewandt auf obiges Beispiel bedeutet dies Folgendes:

Angenommen, die Formel wurde bereits bis zur Zahl $n=k$ bewiesen. Nun soll gezeigt werden, dass die Formel für $n=k+1$ ebenso Gültigkeit besitzt (d. h., nach dem Beispiel soll die Summe $1+2+3+\cdots +k+(k+1)$ berechnet werden).

Die ersten $k$ Summanden bilden eine solche Summe, und zwar für $k$, was kleiner ist als $k+1$. Also darf man – durch die Voraussetzung, dass die Formel für $n=k$ bereits bewiesen ist – diesen Schritt abermals anwenden:

$1+2+3+\cdots +k+(k+1)={\frac {k(k+1)}{2}}+(k+1).$

In diesem Ausdruck wird ($k$+1) ausgeklammert:

$=(k+1)\cdot \left({\frac {k}{2}}+1\right)$

und dies weiter umgeformt zu

$=(k+1)\cdot {\frac {k+2}{2}}$

$={\frac {(k+1)\cdot (k+2)}{2}}$

$={\frac {(k+1)\cdot ((k+1)+1)}{2}}.$

Zu beachten ist, dass $k$ beliebig gewählt werden darf. Beim Vergleich dieses Ausdrucks mit dem zu beweisenden Ausdruck ist festzustellen, dass lediglich $k$ durch $k+1$ ersetzt ist. Damit ist der Schritt von $k$ zu $k+1$ für allgemeine Werte von $k$ bewiesen.

Der große Vorteil des Induktionsbeweises zeigt sich darin, dass die Schritte nicht mehr einzeln durchgeführt werden müssen. Bewiesen werden muss nur, dass eine Aussage für die unterste Zahl (entweder 0 oder 1) gilt, und ebenso, wenn sie bis zu einer beliebigen Zahl gilt, dass sie auch für die nächste Gültigkeit besitzt. (So ist es theoretisch möglich, jede Zahl durch die ständige Anwendung der einzelnen Schritte zu erreichen.)

In der Praxis wird üblicherweise für $n$ und $k$ der gleiche Buchstabe $n$ gewählt. Dies stellt insofern kein Problem dar, solange man sich der unterschiedlichen Bedeutung von $n$ in „$p(n)$ gilt für alle natürlichen Zahlen $n$“ in der zu beweisenden Aussage und „$p(n)$ gilt für ein konkretes $n=k$“ in der Induktionsvoraussetzung bewusst ist. Die Nichtbeachtung führt dazu, dass die zu beweisende Aussage auch als Voraussetzung verwendet wird, und es ergibt sich ein (mathematisch wertloser) Zirkelschluss. Ist die zu beweisende Formel hingegen falsch, so führt der Induktionsschritt nicht zum Ziel, die Formel erfüllt den Induktionsanfang nicht oder es tritt beides auf.

Anderes Beispiel: Summe der ungeraden Zahlen

Es soll eine Formel gefunden werden, welche die Summe aller ungeraden Zahlen von 1 bis $n$ vereinfacht, und diese Formel soll bewiesen werden:

1 = 1

1 + 3 = 4

1 + 3 + 5 = 9

1 + 3 + 5 + 7 = 16

Vermutung: Die Summe aller ungeraden Zahlen von 1 bis $2n-1$ ist gleich dem Quadrat von $n$. Genauer gesagt:

$\sum _{i=1}^{n}(2i-1)=n^{2}.$

Um diese Formel zu beweisen, müssen die folgenden zwei Punkte erfüllt sein:

1. $\sum _{i=1}^{1}(2i-1)=1^{2}.$
2. Wenn $\sum _{i=1}^{n}(2i-1)=n^{2}$, so ist $\sum _{i=1}^{n+1}(2i-1)=(n+1)^{2}.$

Da $\sum _{i=1}^{1}(2i-1)=1=1^{2}$ gilt, ist der erste Punkt erfüllt. Die Richtigkeit des zweiten Punktes zeigt man durch die Identität $\sum _{i=1}^{n+1}(2i-1)=\sum _{i=1}^{n}(2i-1)+(2(n+1)-1)=n^{2}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}$ (Im letzten Schritt wird die erste binomische Formel angewendet).

Damit ist die vollständige Induktion für $\sum _{i=1}^{n}(2i-1)=n^{2}$ abgeschlossen und bewiesen.

Bezeichnungen

Den Beweis der Aussage für die erste Zahl nennt man Induktionsanfang, den Beweis für $n+1$ unter der Annahme (Induktionsannahme, Induktionsvoraussetzung), dass sie bis $n$ gilt, nennt man Induktionsschritt.

Wurden beide Beweisschritte durchgeführt, ist somit die Aussage für alle natürlichen Zahlen bewiesen. In Kurzform:

Gewählt wird eine beliebige, aber feste natürliche Zahl $N$, und man zeigt, dass die Aussage für $N$ wahr ist:

• Die Aussage ist wahr für $n=0$ (Induktionsanfang)
• und deshalb für $n=1$ (Induktionsschritt)
• und deshalb für $n=2$ (Induktionsschritt)
• …
• und deshalb für $n=N$ (Induktionsschritt)

Nach endlich vielen Induktionsschritten gelangt man schließlich zur Aussage für $N$.

Oft wird diese Methode mit dem Dominoeffekt verglichen: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein ein weiterer umgestoßen wird, so fallen schließlich alle Dominosteine.

Indirekte Sichtweise

Eine andere Sichtweise ist die eines indirekten Beweises: Angenommen, die Aussage gelte nicht für alle natürlichen Zahlen. Dann gibt es eine kleinste Zahl $n_{0}$, für die sie falsch ist. Es gibt nun zwei Fälle:

• $n_{0}=0$: Dies wird durch den Induktionsanfang ausgeschlossen.
• $n_{0}\neq 0$: Nach Voraussetzung ist $n_{0}$ die kleinste Zahl, für die die Aussage falsch ist, also ist sie für $n_{0}-1$ wahr. Wendet man nun den Induktionsschritt an, kann man daraus schließen, dass die Aussage auch für $(n_{0}-1)+1=n_{0}$ richtig ist. $n_{0}$ war aber definiert als die kleinste Zahl, für die die Aussage falsch ist: Widerspruch.

Beide Fälle können also ausgeschlossen werden. Damit ist die Aussage für alle natürlichen Zahlen wahr.

Beweis von Ungleichungen

Vollständige Induktion kann auch zum Beweis von Ungleichungen verwendet werden. Diese Beweise sind aber häufig schwieriger als die Beweise von Gleichungen, da sie üblicherweise mehr oder weniger naheliegende Abschätzungen erfordern. Die bernoullische Ungleichung ist ein einfaches Beispiel einer Ungleichung, die sich mit vollständiger Induktion beweisen lässt. Etwas anspruchsvoller ist der Beweis folgender Ungleichung: Für reelle $x_{i}>0\!$, $i=1,\dots ,n$ mit $\prod _{i=1}^{n}x_{i}=1$ folgt, dass $\sum _{i=1}^{n}x_{i}\geq n$.

Die Bedeutung dieser Ungleichung liegt darin, dass sie in weiterer Folge für den Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet werden kann.

• Der Induktionsanfang für den Fall $n=1$ ist offensichtlich. Gilt im Fall $n=2$, dass $x_{1}=x_{2}=1$, so gilt offensichtlich $x_{1}+x_{2}=2\geq 2$. $x_{1}$ und $x_{2}$ können nicht beide größer oder beide kleiner als 1 sein. Nimmt man an, dass $x_{1}\leq 1$ und $x_{2}\geq 1$ gilt, so folgt

$0\leq (1-x_{1})(x_{2}-1)=x_{1}+x_{2}-x_{1}\cdot x_{2}-1=x_{1}+x_{2}-2$

wegen $x_{1}\cdot x_{2}=1$, also

$2\leq x_{1}+x_{2}$. Der Fall $x_{1}\geq 1$ und $x_{2}\leq 1$ ist vollkommen analog zu behandeln.

• Für den Induktionsschritt sei nun $n\geq 2$. Zu zeigen ist, dass für beliebige $n+1$ positive $x_{i}\!$ mit $\prod _{i=1}^{n+1}x_{i}=1$ folgt, dass $\sum _{i=1}^{n+1}x_{i}\geq n+1$. Als Induktionsvoraussetzung darf angenommen werden, dass für $n$ andere beliebige Zahlen (zur einfacheren Unterscheidung nennen wir sie $y_{i}$) aus $\prod _{i=1}^{n}y_{i}=1$ die Ungleichung $\sum _{i=1}^{n}y_{i}\geq n$ folgt.

• Sind alle $x_{i}=1$, so gilt $\sum _{i=1}^{n+1}x_{i}=n+1$, und der Beweis ist fertig. Andernfalls gibt es mindestens ein $x_{i}>1$, sonst wäre das Produkt $\prod _{i=1}^{n+1}x_{i}<1$; ebenso gibt es ein anderes $x_{i}<1$. O. B. d. A. sei also $x_{n}<1$ und $x_{n+1}>1$. Die Bedeutung dieser Wahl wird erst später klar.

Setzt man nun $y_{i}=x_{i}$ für $i=1,\dots ,n-1$ und $y_{n}=x_{n}\cdot x_{n+1}$, so gilt

$\prod _{i=1}^{n}y_{i}=\prod _{i=1}^{n+1}x_{i}=1$.

Somit kann die Induktionsvoraussetzung angewendet werden, und es folgt

$n\leq \sum _{i=1}^{n}y_{i}=\sum _{i=1}^{n-1}x_{i}+x_{n}\cdot x_{n+1}$.

Nun kommt ins Spiel, dass die Indizes $n$ und $n+1$ so gewählt wurden, dass $x_{n}<1$ und $x_{n+1}>1$ gilt. Daraus folgt nämlich

$0\leq \left(1-x_{n}\right)\left(x_{n+1}-1\right)=x_{n}+x_{n+1}-x_{n}\cdot x_{n+1}-1$.

Addiert man die beiden Ungleichungen, so erhält man

$n\leq \sum _{i=1}^{n-1}x_{i}+x_{n}+x_{n+1}-1=\sum _{i=1}^{n+1}x_{i}-1$,

also genau die Behauptung

$n+1\leq \sum _{i=1}^{n+1}x_{i}$.

Tipps zur Anwendung

Es kann sich beim Beweis von Summenformeln mitunter als sehr mühsam erweisen, beim Induktionsschritt von $n$ zu $n+1$ durch Umformungen die Struktur der Ausgangsformel neu zu konstruieren. Dies ist jedoch zur Beweisführung unerlässlich. Da ist es dann manchmal hilfreich, das Pferd von hinten aufzuzäumen. Beispielsweise ist das Ausmultiplizieren und Zusammenfassen von Gliedern oftmals leichter zu bewerkstelligen als das phantasievolle Aufspalten und Umordnen von Gliedern, um etwas ausklammern zu können. Um diesen Umstand zu nutzen, setzt man in die zu beweisende Formel $n+1$ für $n$ ein und versucht, durch äquivalente Umformungen die Ausgangsformel für $n$ zu isolieren. Da die Formel für $n$ laut Voraussetzung gilt, ist der Beweis geführt, sobald das, was bei den äquivalenten Umformungen außer der isolierten Formel z. B. als Summand oder als zusätzlicher Faktor entsteht, dem entspricht, was beim Induktionsschritt hinzugefügt wird.

Häufige Fehler

Beim Beweis durch Induktion treten zwei Fehler besonders häufig auf.

• Der Induktionsschritt funktioniert zwar, die Behauptung gilt für die Anfangsbedingung aber nicht. Man könnte z. B. behaupten, dass

  $1+2+3+\cdots +n={\frac {n(n+1)}{2}}+7$.

  Falls diese Behauptung für ein n gelten würde, dann würde sie auch für $n+1$ gelten! Da sich aber kein solches $n$ für einen Induktionsanfang finden lässt, ist der Induktionsbeweis falsch!

• Der Induktionsschritt ist nicht für alle $n$ gültig, d. h., es gibt mindestens ein $n\geq n_{0}$ (der Verankerung), für das er nicht anwendbar ist. Hier ein Beispiel für so einen falschen Beweis:

  Behauptung: Alle Zahlen sind gleich.

  Beweis: Wir vergleichen Mengen von Zahlen, dabei sei $n$ die Anzahl der Elemente der Menge.

  Induktionsbeginn: Für $n=1$ sind alle Elemente der Menge gleich, es gibt ja nur eines!

  Induktionsvoraussetzung: Angenommen, in einer Menge mit $n$ Zahlen sind stets alle Zahlen gleich.

  Induktionsschritt: Dann sind auch alle Zahlen in einer Menge mit $n+1$ Zahlen gleich, denn: Entfernt man aus der $n+1$-elementigen Menge eine Zahl $x$, dann erhalten wir eine $n$-elementige Menge, in der nach Voraussetzung alle Zahlen gleich sind. Fügen wir $x$ wieder hinzu und entfernen eine andere Zahl $y$, dann sind wieder alle Zahlen der Restmenge gleich. Es folgt, dass $x=y$ gelten muss, also sind alle Zahlen der Menge gleich.

  Der Fehler liegt darin, dass man nur dann verschiedene Zahlen $x$ und $y$ entfernen kann,

  wenn die Menge mindestens 2 Elemente hat ($n\geq 2$).

  Der Schluss von $n$ auf $n+1$ ist also nur für $n\geq 2$ korrekt. Dass die Behauptung für $n=1$ richtig ist, hilft nicht, da auf diesen Fall der Induktionsschritt nicht anwendbar ist.

Anwendungen

Baut man die natürlichen Zahlen auf den Peano-Axiomen auf, so werden die arithmetischen Grundgesetze wie Assoziativgesetz, Kommutativgesetz und Distributivgesetz für die Addition und Multiplikation natürlicher Zahlen mit vollständiger Induktion bewiesen. Eine ausführliche Ausarbeitung dieser Beweise findet sich in Edmund Landau: Grundlagen der Analysis (Das Rechnen mit ganzen, rationalen, irrationalen, komplexen Zahlen), Leipzig 1930.

Weitere wichtige mathematische Sätze, die üblicherweise mit Induktion bewiesen werden, sind beispielsweise der binomische Lehrsatz und die bernoullische Ungleichung.

Verallgemeinerungen und Variationen

Beweis für fast alle natürlichen Zahlen

Der Induktionsbeweis ist auch für Aussagen möglich, die nicht für alle natürlichen Zahlen, sondern nur für alle Zahlen ab einem gewissen Startwert gelten. So lässt sich beispielsweise für die Ungleichung $2^{n}\geq n^{2}$ der Induktionsschritt für $n\geq 3$ durchführen:

$2^{n+1}=2\cdot 2^{n}\geq 2n^{2}$ laut Induktionsvoraussetzung,

$2n^{2}=n^{2}+n^{2}\geq n^{2}+3n>n^{2}+2n+1=(n+1)^{2}$ für $n\geq 3$.

Die Ungleichung ist allerdings für $n=3$ falsch, gilt aber für $n=4$; der Induktionsbeweis zeigt also die Gültigkeit der Ungleichung für $n\geq 4$. Die endlich vielen Fälle, die durch den Induktionsbeweis nicht abgedeckt sind, können einzeln untersucht werden.

Beweis für ganze (positive und negative) Zahlen

Der Induktionsbeweis ist auch für Aussagen möglich, die nicht nur für alle natürlichen Zahlen, sondern auch für alle negativen Zahlen gelten. Dafür beginnt man z. B. mit dem Startwert 0 und beweist einmal den Induktionsschluss $n\rightarrow n+1$ für die positiven Zahlen und anschließend $n\rightarrow n-1$ für die negativen Zahlen.

Verwendung mehrerer Vorgänger

Manchmal ist es notwendig, für den Beweis der Aussage für $n+1$ die Gültigkeit sowohl für $n$ als auch für $n-1$ (oder für noch mehr Vorgänger) vorauszusetzen. Der Induktionsanfang muss dann allerdings für mehrere Startwerte (also z. B. $n=0$ und $n=1$) durchgeführt werden, da ja beispielsweise für den Induktionsschritt für $n=1$ auch die Voraussetzung für $n=-1$ benötigt würde. Ein Beispiel wäre der Beweis der Formeln von Binet

$f_{n}={\frac {1}{\sqrt {5}}}(a^{n}-b^{n})$ mit $a={\frac {1+{\sqrt {5}}}{2}}$ und $b={\frac {1-{\sqrt {5}}}{2}}$

für die Fibonacci-Folge $f_{n}$.

Vorwärts-rückwärts-Induktion

Eine andere Variante ist die „Vorwärts-rückwärts-Induktion“. Dabei wird in einem Vorwärtsschritt die Aussage für beliebig große Zahlen bewiesen, indem z. B. von $n$ auf $2n$ geschlossen wird. Danach werden die Lücken mit einem Rückwärtsschritt geschlossen, in dem z. B. aus der Gültigkeit für $n$ die Gültigkeit für $n-1$ bewiesen wird. Diese Technik wurde beispielsweise von Augustin Louis Cauchy, in Cours d’analyse de l’Ecole Royale Polytechnique, premier partie, Analyse algebrique, Paris 1821, S. 457ff zum Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet.

Ein weiteres Beispiel ist die jensensche Ungleichung, deren Beweis mit vorwärts-rückwärts-Induktion 1905 von Johann Ludwig Jensen bei einer Konferenz der Dänischen Mathematischen Gesellschaft präsentiert wurde.

Sonstige

Eine andere Verallgemeinerung wäre, als Induktionsvoraussetzung nicht nur eine Aussage für die Zahl $n$ zu verwenden, sondern eine Aussage für alle Zahlen $m$ mit $0\leq m\leq n$. D.h., man darf beim Beweis für $n+1$ annehmen, dass die Aussage für alle $m\leq n$ gilt. Dies eröffnet der Beweisführung mehr Möglichkeiten.

Aus rechentechnischen Gründen wird oft als Induktionsschritt nicht von $n$ auf $n+1$ geschlossen sondern von $n-1$ auf $n$. Dies ist allerdings lediglich eine Notationsänderung, die manchmal die Umformungen vereinfacht, aber ansonsten keinen Unterschied macht.

Wenn man zu allgemeineren Mengen übergehen will, so zeigt sich, dass die vollständige Induktion auf allen Mengen anwendbar ist, auf denen eine partielle Ordnung definiert ist, wobei keine unendlichen absteigenden Ketten auftreten dürfen (weil sonst keine Anfangselemente gefunden werden können). Eine solche Menge heißt fundierte Menge.

Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen können unendlich und größer werden). In diesem Fall wird die Methode transfinite Induktion genannt. Sie ist wichtig in der Mengenlehre und der Topologie.

In der Metamathematik verwendet man eine so genannte unendliche Induktion (auch $\omega$-Regel genannt). In halbformalen Systemen der Mathematik lassen sich damit Vollständigkeitsbeweise und Widerspruchsfreiheitsbeweise durchführen.

Weblinks

• http://henked.de/begriffe/induktion.htm Vollständige Induktion