Vollständige Induktion

aus Wikipedia, der freien Enzyklopädie

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

[Bearbeiten] 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.

[Bearbeiten] Historisches

Die vollständige Induktion findet sich erstmals 1575 in dem Werk Arithmeticorum Libri Duo bei Franciscus Maurolicus, 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.

[Bearbeiten] Definition

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

Ist

K

eine Teilmenge von $\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 $\N$ .

(Ob man bei 0 oder 1 beginnt, hängt davon ab, ob 0 als Element von $\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 mit $k$ auch $k + 1$ in der Menge $K$ liegt. Nach dem Induktionsaxiom gilt deshalb $K = \N$ , und die Aussage $p (n)$ besitzt für alle natürlichen Zahlen $n\ge 1$ Gültigkeit.

[Bearbeiten] 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, dass die Aussage für sämtliche natürlichen Zahlen richtig ist.

[Bearbeiten] Übersicht und Bezeichnungen

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

Induktionsanfang,
Induktionsannahme oder Induktionsvoraussetzung,
Induktionsschluss oder Induktionsschritt.

[Bearbeiten] 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 natürlichen Zahlen $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 wurden beide Beweisschritte durchgeführt, ist die Aussage für alle natürlichen Zahlen bewiesen, denn für eine beliebige natürliche Zahl $N$ folgt, dass die Aussage für $N$ wahr ist:

Die Aussage ist wahr für $1$ (Induktionsanfang)
und deshalb für $2$ (Induktionsschritt)
und deshalb für $3$ (Induktionsschritt)
…
und deshalb für $N$ (Induktionsschritt)

Nach endlich vielen Induktionsschritten gelangt man schließlich zur Aussage für $N$ . Weil $N$ beliebig gewählt wurde, ist damit die Aussage für jede natürliche Zahl bewiesen.

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 wird schließlich jeder Dominostein irgendwann umfallen.

[Bearbeiten] 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 = 1$ : Dies wird durch den Induktionsanfang ausgeschlossen.
$n_0\ne1$ : 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.

[Bearbeiten] Beispiel

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

Für einzelne Zahlen ist die Formel leicht nachzurechnen:

Für $n = 1$ :

$\sum^1_{k=1} k = 1 = \frac{1(1+1)}{2}$
Für $n = 2$ :

$\sum^2_{k=1} k = 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.

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 Zirkelschluss ohne jede Beweiskraft. 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.

[Bearbeiten] Anderes Beispiel: Summe der ungeraden Zahlen

Es soll eine Formel gefunden werden, welche die Summe der ersten $n$ ungeraden Zahlen 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 $2 n - 1$ ist gleich dem Quadrat von $n$ . Genauer gesagt:

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

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

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

Da $\sum^1_{i=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^{n+1}_{i=1} (2i-1) = \sum^n_{i=1} (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^n_{i=1} (2i-1) = n^2$ abgeschlossen und bewiesen.

[Bearbeiten] 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 Abschätzungen erfordern, die nicht immer offensichtlich sind. 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\leq1$ und $x_2\geq1$ 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\geq1$ und $x_2\leq1$ 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$ .

[Bearbeiten] 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.

[Bearbeiten] Häufige Fehler

Beim Beweis durch vollständige 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\ge 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\ge 2$ ).

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

[Bearbeiten] 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.

[Bearbeiten] Verallgemeinerungen und Variationen

[Bearbeiten] 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\ge n^2$ der Induktionsschritt für $n\ge 3$ durchführen:

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

$2n^2 =n^2+n^2\ge n^2+3n > n^2+2n+1=(n+1)^2$ für $n\ge 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\ge 4$ . Die endlich vielen Fälle, die durch den Induktionsbeweis nicht abgedeckt sind, können einzeln untersucht werden.

[Bearbeiten] 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 mit einem beliebigen Startwert, zum Beispiel 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. Bei 0 als Startwert kann man für die negativen Zahlen alternativ auch $n \rightarrow -n$ zeigen.

[Bearbeiten] Beweis für rationale Zahlen

Da man alle rationalen Zahlen als Bruch $\dfrac{p}{q}$ , mit $p \in\Z, q\in\N$ , also mit positivem Nenner, darstellen kann, kann man auch eine vollständige Induktion über die rationalen Zahlen durchführen. Als Induktionsanfang wird eine beliebige ganze Zahl verwendet $\left(\dfrac{p}{1}\right)$ . Dann sind drei Induktionsschritte nötig: $\dfrac{p}{q} \rightarrow \dfrac{p+1}{q},~\dfrac{p}{q} \rightarrow \dfrac{p-1}{q}$ und $\dfrac{p}{q} \rightarrow \dfrac{p}{q+1}$ . Die ersten beiden Induktionsschritte zeigen, dass, wenn die zu zeigende Aussage für eine rationale Zahl mit Nenner $q$ gilt, die Aussage für alle rationalen Zahlen mit diesem Nenner gilt. Der dritte Induktionsschritt zeigt, dass, wenn die Aussage für eine rationale Zahl mit Zähler $p$ gilt, sie für alle Zahlen mit diesem Zähler gilt. Damit gilt die Aussage für alle rationalen Zahlen. Da vor allem der letzte Induktionsschritt etwas komplizierter werden kann, wird dieses Verfahren nur selten angewandt.

[Bearbeiten] 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$ .

[Bearbeiten] 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 $2 n$ 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.^[1]

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^[2].

[Bearbeiten] 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, man führt sozusagen den Schritt $\le n$ nach $n$ durch. Dies eröffnet der Beweisführung mehr Möglichkeiten. Die Gültigkeit dieser Art der Induktion lässt sich mit Hilfe der vollständigen Induktion beweisen, man nennt sie auch Induktion zweiter Art.

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 $ω$ -Regel genannt). In halbformalen Systemen der Mathematik lassen sich damit Vollständigkeitsbeweise und Widerspruchsfreiheitsbeweise durchführen.

[Bearbeiten] Quellen

↑ Cauchy, Augustin-Louis. Analyse algébrique. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel mittels Vorwärts-rückwärts-Induktion findet sich auf Seite 457ff.
↑ Jensen, J. L. W. V. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. In Acta Math. 30, 175–193, 1906.

[Bearbeiten] Weblinks

http://henked.de/begriffe/induktion.htm Vollständige Induktion
http://www.emath.de/Referate/Induktion-Aufgaben-Loesungen.pdf Umfangreiche Aufgabensammlung zur vollständigen Induktion mit Lösungen

Dieser Artikel wurde in die Liste der lesenswerten Artikel aufgenommen.

[0] Cauchy, Augustin-Louis. Analyse algébrique. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel mittels Vorwärts-rückwärts-Induktion findet sich auf Seite 457ff.

[1] Jensen, J. L. W. V. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. In Acta Math. 30, 175–193, 1906.

[1]

[2]