Vollständige Induktion

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann solch ein Beweis nicht für jede Zahl einzeln erbracht werden. Er wird daher in zwei Etappen durchgeführt: als Induktionsanfang für eine kleinste Zahl (meist 1 oder 0) und als Induktionsschritt, der aus der Aussage für eine variable Zahl die entsprechende Aussage für die nächste Zahl logisch ableitet. Damit ist schon die Gültigkeit der Aussage für alle natürlichen Zahlen gezeigt.

Die Beweismethode beruht auf dem Prinzip der vollständigen Induktion (kurz: Induktionsprinzip), das entweder als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden kann. Die vollständige Induktion ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik. Trotz ihres Namens handelt es sich bei der vollständigen Induktion um ein deduktives Verfahren.

Beschreibung

Um zu beweisen, dass eine Aussage <math>A(n)</math> für alle natürlichen Zahlen <math>n</math> gilt, genügt es, Folgendes zu zeigen:<ref>Vorlage:Literatur</ref>

1. Es gilt <math>A(0)</math> bzw. <math>A(1)</math>.<ref group="A">Ob der Induktionsanfang bei <math>n=0</math> oder bei <math>n=1</math> startet, hängt davon ab, ob man die Null zu den natürlichen Zahlen zählt oder nicht.</ref> (Induktionsanfang, Induktionsverankerung)
2. Für beliebiges <math>n</math> folgt aus der Gültigkeit von <math>A(n)</math> die Gültigkeit von <math>A(n+1)</math>. (Induktionsschritt, Induktionsschluss, Schluss von n auf n+1)

Im Induktionsschritt geht man so vor, dass man zunächst für ein beliebiges <math>n</math> die Gültigkeit von <math>A(n)</math> voraussetzt (Induktionsvoraussetzung oder Induktionsannahme) und darauf basierend zeigt, dass <math>A(n+1)</math> gilt (Induktionsbehauptung).

Veranschaulichung

Datei:Domino - 2.png

Vollständige Induktion als Dominoeffekt mit unendlich vielen Steinen

Die Methode der vollständigen Induktion ist mit dem Dominoeffekt vergleichbar: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein der nächste umgestoßen wird, wird schließlich jeder Dominostein der unendlich lang gedachten Kette irgendwann umfallen.<ref>Vorlage:Literatur</ref>

Die Allgemeingültigkeit einer Aussageform <math>A(n)</math> ist für <math>n = 1, 2, 3, \ldots</math> bewiesen, wenn <math>A(1)</math> gültig ist (der erste Stein fällt um) und wenn zusätzlich gilt <math>A(n) \Rightarrow A(n+1)</math> für <math>n = 1, 2, 3, \ldots</math> (jeder Stein stößt beim Umfallen den nächsten Stein mit um).

Beispiele

Gaußsche Summenformel

Vorlage:Hauptartikel Die Gaußsche Summenformel besagt: Für alle natürliche Zahlen <math>n \geq 1 </math> gilt

<math>1+2+\cdots+n = \frac{n(n+1)}{2}</math>.

Der Induktionsanfang ergibt sich unmittelbar:

<math>1 = \frac{1(1+1)}{2}</math>

Im Induktionsschritt ist zu zeigen, dass für <math>n \geq 1</math> aus der Induktionsvoraussetzung

<math>1+2+\cdots+n = \frac{n(n+1)}{2}</math>

die Induktionsbehauptung

<math>1+2+\cdots+n+(n+1) = \frac{(n+1)((n+1)+1)}{2}</math>

(mit <math>(n\!+\!1)</math> an der Stelle des <math>n</math> der Induktionsvoraussetzung) folgt.

Dies gelingt, indem man die linke Seite der Induktionsbehauptung zunächst mithilfe der Induktionsvoraussetzung umformt und dann elementare Termumformungen vornimmt:

<math>

\begin{align}1+2+\cdots+n+(n+1) &= \frac{n(n+1)}{2} + (n+1) \\ &= \frac{n(n+1)+2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2} \\ &= \frac{(n+1)((n+1)+1)}{2}.

\end{align} </math>

Mit dem Induktionsprinzip folgt die Gültigkeit der Gaußschen Summenformel für alle <math>n \geq 1</math>.

Summe ungerader Zahlen (Maurolicus 1575)

Die schrittweise Berechnung der Summe der ersten <math> n </math> ungeraden Zahlen,

<math>1=1</math>

<math>1+3=4</math>

<math>1+3+5=9</math>

<math>1+3+5+7=16</math>,

legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von <math> 1 </math> bis <math> 2n-1</math> ist gleich dem Quadrat von <math>n</math>:

<math>1+3+5+ \cdots + (2n-1) = n^2</math>.

Sie wurde 1575 von Franciscus Maurolicus mit vollständiger Induktion bewiesen.<ref name="Maurolicus">Maurolycus: Arithemticorum Liber primus, S. 7, Proposition 15^a. Vorlage:Google Buch.</ref> Ein Beweis mit moderner Notation liest sich folgendermaßen:

Der Induktionsanfang mit <math>n=1</math> gilt wegen <math>1 =1^2</math>.

Im Induktionsschritt ist zu zeigen, dass aus der Induktionsvoraussetzung

<math>\textstyle 1+3+5+ \cdots +(2n-1) = n^2 </math> für ein <math>n\geq 1</math>

die Induktionsbehauptung

<math>\textstyle 1+3+5+ \cdots + (2(n+1)-1) = (n+1)^2</math>

folgt. Er ergibt sich über folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:

<math>\begin{align}

1+3+5+\cdots + (2(n+1)-1) &= 1 + 3 + 5 + \cdots + (2n-1) + (2(n+1)-1) \\

    & = n^2 + 2n + 1 \\
    & = (n+1)^2.

\end{align}</math> Mit dem Induktionsprinzip folgt die Gültigkeit der Aussage für alle <math>n \geq 1</math>.

Bernoullische Ungleichung

Nach der Bernoullische Ungleichung gilt für alle reellen Zahlen <math>x \geq -1</math> und alle natürlichen Zahlen <math>n \geq 0</math> die Ungleichung

<math>(1+x)^n \geq 1+nx</math>.

Der Induktionsanfang mit <math>n=0</math> gilt wegen <math> (1+x)^0 = 1 \geq 1 </math>.<ref group="A">Für <math>x=-1</math> muss <math>0^0 :=1</math> gesetzt werden, damit die Bernoulli-Ungleichung ihre Gültigkeit auch für diesen Fall behält.</ref>

Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei die Bedingung <math>x \geq -1</math> dafür sorgt, dass der Term nicht negativ wird:

<math>\begin{align}

(1+x)^{n+1} &= {(1+x)^n } \cdot (1+x) \\ &\geq (1+nx) \cdot(1+x) \\ &= 1 + x + nx + nx^2 \\ &\geq 1 + x + nx \\ &= 1 + (n+1)x. \end{align}</math> Nach dem Induktionsprinzip gilt die Behauptung für alle <math>n \in \mathbb N_0</math>.

Pferde-Paradox

Vorlage:Hauptartikel Das Pferde-Paradox ist ein Standardbeispiel für eine fehlerhafte Anwendung der vollständigen Induktion und illustriert die Bedeutung des Zusammenspiels von Induktionsverankerung und Induktionsschritt. Bei ihm wird die unsinnige Aussage, dass in einer Herde von <math>n</math> Pferden alle immer die gleiche Farbe besitzen, anhand einer scheinbar korrekten Induktion bewiesen. Dabei ist der Induktionsschritt selbst korrekt, würde aber die Induktionsverankerung bei einem <math>n\geq 2</math> benötigen, während der (fehlerhafte) Beweis die Induktion bei <math>n=1</math> verankert und somit schon der Schritt von <math>n=1</math> auf <math>n=2</math> scheitert.

Etymologie und Geschichte

Die Bezeichnung Induktion leitet sich ab von lat. inductio, wörtlich „Hineinführung“. Der Zusatz vollständig signalisiert, dass es sich hier im Gegensatz zur Induktion im Sinne der Philosophie, die aus Spezialfällen ein allgemeines Gesetz erschließt und kein exaktes Schlussverfahren ist, um ein deduktives Beweisverfahren handelt.

Das Induktionsprinzip steckt latent bereits in der von Euklid überlieferten pythagoreischen Zahlendefinition: „Zahl ist die aus Einheiten zusammengesetzte Menge.“<ref name="Euklid">Euklids Elemente VII, Definition 2. Dazu: Wilfried Neumaier: Antike Rhythmustheorien, Kap. 1 Antike mathematische Grundbegriffe, S. 11–12.</ref> Euklid führte aber noch keine Induktionsbeweise, sondern begnügte sich mit intuitiven, exemplarischen Induktionen, die sich aber vervollständigen lassen. Auch andere bedeutende Mathematiker der Antike und des Mittelalters hatten noch kein Bedürfnis nach präzisen Induktionsbeweisen. Vereinzelte Ausnahmen im hebräischen und arabischen Sprachraum blieben ohne Nachfolge.<ref>Vorlage:Literatur</ref><ref>Vorlage:Literatur</ref>

Lange galt ein Beweis von Franciscus Maurolicus von 1575 als älteste explizite vollständige Induktion (unten ausgeführt).<ref name="Maurolicus" /> Er erörterte aber das allgemeine Beweisverfahren noch nicht. Erst Blaise Pascal thematisierte das Induktionsprinzip mit Induktionsanfang und Induktionsschritt in seinem Traité du triangle arithmétique von 1654.<ref>Blaise Pascal: Traité du triangle arithmétique, S. 7, Conséquence douziesme, Le 1. (Induktionsanfang), Le 2. (Induktionsschritt), Vorlage:Google Buch.</ref> Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob I Bernoulli wesentlich bei.<ref>Vorlage:Literatur</ref>

Das Beweisverfahren wurde dann 1838 von Augustus De Morgan erstmals als Induktion oder sukzessive Induktion bezeichnet.<ref name="De Morgan">Vorlage:Literatur</ref> 1888 prägte schließlich Richard Dedekind in seiner Schrift Was sind und was sollen die Zahlen? den Begriff vollständige Induktion.<ref name="Dedekind">Vorlage:Literatur</ref> Über dieses Werk aus der Gründerzeit der Mengenlehre wurde sie zum allgemein bekannten, etablierten Beweisprinzip, auf das seither kein Zweig der Mathematik mehr verzichten kann. Ein Jahr später, 1889, formulierte Giuseppe Peano mit den Peanoschen Axiomen den ersten formalisierten Kalkül für die natürlichen Zahlen mit einem Induktionsaxiom, aus dem sich das Beweisschema der vollständigen Induktion herleiten lässt.<ref>Vorlage:Literatur</ref> Er zeigte mit formaler Strenge, dass aus seinen Zahlaxiomen, zu denen das Induktionsaxiom gehört, die ganze Arithmetik bis hin zu den reellen Zahlen ableitbar ist. Dadurch machte er die fundamentale Bedeutung und die Leistungskraft der Induktion voll bewusst.

Prinzip der vollständigen Induktion

Das Beweisverfahren der vollständigen Induktion beruht auf dem Prinzip der vollständigen Induktion:<ref name=":1" />

Ist <math>A(n)</math> eine Aussage über natürliche Zahlen, so dass

1. <math>A(0)</math> bzw. <math>A(1)</math> gilt und
2. für alle <math>n</math> die Gültigkeit von <math>A(n)</math> die Gültigkeit von <math>A(n+1)</math> nach sich zieht,

so gilt die Aussage für jede natürliche Zahl.

Als formale Schlussregel mit dem Ableitungsoperator <math>\vdash</math> lautet das Prinzip der vollständigen Induktion:

<math>A(0) \land \forall n \in \N\colon(A(n)\Rightarrow A(n+1))\ \vdash\ \forall n \in \N \colon A(n)</math>

Logische Stellung des Induktionsprinzips

Das Induktionsprinzip kann entweder als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden. Im Rahmen der Arithmetik und Zahlentheorie wird es meist aus dem gleichwertigen fünften Peano-Axiom, dem Induktionsaxiom, hergeleitet.<ref>Vorlage:Literatur</ref> Dieses lautet:

Ist <math>\,K</math> eine Teilmenge der natürlichen Zahlen <math>\N</math> mit den Eigenschaften:

1. <math>\,1</math> ist ein Element von <math>\,K</math>
2. Mit <math>\,n </math> aus <math>\,K </math> ist stets auch <math>\,n+1 </math> aus <math>\,K </math>,

dann ist <math>\,K = \N</math>.

Auch in anderen Konzepten der natürlichen Zahlen sind die Peano-Axiome und damit auch das Prinzip der vollständigen Induktion herleitbar, zum Beispiel bei der Definition der natürlichen Zahlen

• als von 1 erzeugte geordnete Halbgruppe, die der zitierten pythagoreischen Zahlendefinition entspricht;<ref name="Euklid" />
• als frei von 1 erzeugtes Monoid, das von der Addition der Zahlen ausgeht;<ref>Felscher: Naive Mengen und abstrakte Zahlen I, S. 130–132.</ref>
• als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht;<ref>Dedekind: Was sind und was sollen die Zahlen?, § 6, Erklärung 71.</ref><ref>dargestellt als Dedekind-Tripel in: Felscher: Naive Mengen und abstrakte Zahlen I, S. 147.</ref>
• als kleinste induktive Menge, nämlich als kleinste Menge, die das Unendlichkeitsaxiom erfüllt, wie es in der Mengenlehre üblich ist;
• als Klasse der endlichen Ordinalzahlen, die nur eine allgemeine Mengenlehre ohne Unendlichkeitsaxiom voraussetzt.

Induktionsvarianten

Induktion mit beliebigem Anfang

Möchte man zeigen, dass eine Aussage <math>A(n)</math> nicht für alle natürlichen Zahlen, sondern nur für natürliche Zahlen größer oder gleich einer Zahl <math>n_0</math> gilt, so besteht ein Induktionsbeweis aus den beiden folgenden Schritten:<ref>Vorlage:Literatur</ref>

1. Im Induktionsanfang zeigt man, dass die Aussage für <math>n_0</math> gilt.
2. Im Induktionsschritt zeigt man, dass für beliebiges <math>n \geq n_0</math> gilt: Ist die Aussage für <math>n</math> richtig, so auch für <math>n+1</math>.

Beispiel

Induktionsbeweis der Ungleichung <math>2^n\ge n^2</math> für natürliche Zahlen <math>n\ge 4</math>: Induktionsanfang: Für <math>\,n = 4</math> ist die Ungleichung wegen <math>2^{4}=16\ge 16 = 4^2</math> erfüllt. Induktionsschritt: Für ein <math>n \geq 4</math> gelte <math>2^n \geq n^2 </math> (Induktionsvoraussetzung). Damit erhält man die Abschätzung

<math>\begin{array}{lll}

2^{n+1} &= 2\cdot 2^n\ge 2\cdot n^2 &= n^2+n\cdot n \ge n^2+4n \\ &= n^2+2n+2n &\ge n^2+2n+2\cdot4 \\ &\ge n^2+2n+1 &= (n+1)^2 . \end{array}</math>

Dabei wurde die Induktionsvoraussetzung im zweiten Schritt verwendet und im vierten und sechsten Schritt die Voraussetzung <math>n \geq 4</math>. Die endlich vielen Fälle, die solch ein allgemeinerer Induktionsbeweis nicht abdeckt, können einzeln untersucht werden. Im Beispiel ist die Ungleichung für <math>n=3</math> offenbar falsch.

Induktion mit mehreren Vorgängern

In manchen Induktionsbeweisen kommt man in der Induktionsvoraussetzung mit dem Bezug auf einen einzigen Vorgänger nicht aus, bspw. wenn eine Rekursionsformel mehrere Vorgänger enthält.<ref>S. Beweis der Formel von Binet für die Fibonacci-Folge</ref> Der Induktionsanfang ist dann für mehrere Startwerte durchzuführen. Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung für <math>n</math> und <math>n-1</math> nötig, dann ist ein Induktionsanfang für zwei aufeinander folgende Zahlen, also etwa 0 und 1, erforderlich.

Starke Induktion

Die starke Induktion beruht auf dem Prinzip der starken Induktion, das Folgendes besagt:<ref name=":0">Vorlage:Literatur</ref><ref>Vorlage:Literatur</ref>

Zieht für jedes <math>k</math> die Gültigkeit der Aussagen <math>A(1), A(2), \ldots , A(k-1)</math> die Gültigkeit von <math>A(k)</math> nach sich, so gilt <math>A(n)</math> für alle natürlichen Zahlen.

Bei einem Beweis mittels starker Induktion ist folglich nur der Induktionsschritt zu zeigen. Hierzu setzt man voraus, dass für beliebiges <math>k</math> die Aussage <math>A(1), A(2), \ldots , A(k-1)</math> gelten (starke Induktionsvoraussetzung), und zeigt dann die Gültigkeit von <math>A(k)</math> (Induktionsbehauptung).

Das Prinzip der „gewöhnlichen“ Induktion<ref group="A">Um die gewöhnliche Induktion von der starken Induktion abzugrenzen, spricht man auch von der schwachen Induktion.</ref> ist äquivalent zum Prinzip der starken Induktion, das heißt beide Prinzipien lassen sich jeweils aus dem anderen folgern.<ref name=":0" /><ref name=":1">Vorlage:Literatur</ref> Trotz dieser prinzipiellen Gleichwertigkeit in der Beweisstärke ist der Unterschied in der Ausdrucksstärke wegen der beliebig vielen Startwerte und der Möglichkeit des Rückgriffs auf beliebig viele Vorgänger groß, besonders bei rekursiven Definitionen.

Beispiel

Ein Beispiel ist der Beweis, dass jede natürliche Zahl <math>n\geq 2</math> einen Primzahl-Teiler hat:

Die Aussage sei für alle <math>m</math> mit <math>2\leq m \leq n</math> erfüllt. Ist nun <math>n+1</math> eine Primzahl, so ist <math>n+1</math> selbst der gesuchte Teiler, und die Behauptung ist bewiesen. Ist <math>\,n+1</math> keine Primzahl, so gibt es zwei Zahlen <math>a, b \in\N</math> mit <math>a\cdot b = n+1</math> und <math>1 < a < n+1</math>. In diesem Fall besitzt <math>a</math> gemäß Induktionsvoraussetzung einen Primzahl-Teiler, etwa <math>p</math>. Dann teilt <math>p</math> auch <math>n+1</math> und ist Primzahl-Teiler von <math>n+1</math>. Damit ist auch für diesen zweiten Fall die Behauptung bewiesen.

Induktion mit Vorwärts-Rückwärts-Schritten

Augustin-Louis Cauchy führte 1821 eine Induktionsvariante vor, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (nämlich von <math>2^k</math> nach <math>2^{k+1}</math>) und die entstandenen Lücken nachträglich durch eine rückwärts gerichtete Herleitung von <math>2^k</math> nach <math>n < 2^k</math> auf einen Schlag gefüllt werden. Mit dieser Variante bewies er die Ungleichung vom arithmetischen und geometrischen Mittel.<ref>Vorlage:Literatur</ref>

Weitere Induktionsvarianten

Es gibt auch Sachlagen, bei denen Aussagen über alle ganzen Zahlen (positive und negative) mit vollständiger Induktion bewiesen werden können. Der Beweis in die positive Richtung geschieht wie gewohnt mit einem beliebigen Induktionsanfang und dem positiven Induktionsschritt von <math>n</math> nach <math>n+1</math>. Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von <math>n</math> nach <math>n-1</math> auszuführen. Beispielsweise lässt sich bei der Fibonacci-Folge die Rekursionsgleichung in die Gegenrichtung umstülpen.

Die vollständige Induktion lässt sich auf Ordinalzahlen verallgemeinern. Bei Ordinalzahlen, die größer als die natürlichen Zahlen sind, spricht man dann von transfiniter Induktion.<ref>Vorlage:Literatur</ref>

Die Induktion lässt sich auch übertragen auf sogenannte fundierte Mengen, die eine der Zahlenordnung vergleichbare Ordnungsstruktur aufweisen; hier spricht man zuweilen von struktureller Induktion.

Rekursive oder induktive Definition

Die rekursive Definition<ref>Vorlage:Literatur</ref> – auch induktive Definition genannt<ref name="Hausdorff">Vorlage:Literatur</ref><ref>Vorlage:Literatur</ref> – ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird. Dadurch ist der Term schon für alle natürlichen Zahlen erklärt.

Beispiel

Die Potenzen einer Zahl <math>x</math> sind erklärt durch

1. <math>x^1 := x</math> und
2. die Rekursionsformel <math>x^{n+1} := x^n\cdot x</math>

Anmerkungen

<references group="A" />

Literatur

• Otto Forster, Florian Lindemann: Analysis 1. 13. Auflage. Springer Spektrum, Wiesbaden 2023, ISBN 978-3-658-40129-0, S. 1–24.
• Konrad Königsberger: Analysis 1. 6. Auflage. Springer, Berlin 2004, ISBN 978-3-540-40371-5, S. 1–2.
• Gerhard Schurz: Logik: Grund- und Aufbaukurs in Aussagen- und Prädikatenlogik. 2. Auflage. De Gruyter, Berlin / Boston 2020, ISBN 978-3-11-069714-8, S. 357–360.
• Florian André Dalwigk: Vollständige Induktion. Springer, Berlin / Heidelberg 2019, ISBN 978-3-662-58632-7
• Vorlage:Literatur
• Ilja S. Sominski: Die Methode der vollständigen Induktion (= Kleine Ergänzungsreihe zu den Hochschulbüchern Mathematik. Band 3). 10. Auflage. VEB Deutscher Verlag der Wissenschaften, Berlin 1971.
• David S. Gunderson: Handbook of Mathematical Induction. Taylor & Francis, 2010, ISBN 978-1-4200-9365-0.

Weblinks

• Vollständige Induktion mit Beispielen.
• Vollständige Induktion. henked.de
• emath.de (PDF; 837 kB) Umfangreiche Aufgabensammlung zur vollständigen Induktion
• Joachim Mohr: Crashkurs in die vollständige Induktion. kilchb.de
• Christian Spannagel: Vorlesungen zur vollständigen Induktion.
• Beweise mit vollständiger Induktion auf Video anschaulich erklärt:
  • Vorlage:YouTube.
  • Vorlage:YouTube.
  • Vorlage:YouTube.
  • Vorlage:YouTube.

Einzelnachweise

<references />

Kategorie:Mathematischer Grundbegriff Kategorie:Beweis (Mathematik) Kategorie:Wikipedia:Artikel mit Video