~2025-26902-00: /* Induktion mit beliebigem Anfang */ Überflüssiges Wort

2025-09-27T21:02:56Z

Induktion mit beliebigem Anfang: Überflüssiges Wort

Neue Seite

Die '''vollständige Induktion''' ist eine [[Beweis (Mathematik)|mathematische Beweismethode]], nach der eine [[Logische Aussage|Aussage]] für alle [[Natürliche Zahl|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 [[Deduktion#Mathematische Logik und formale Systeme|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>{{Literatur |Autor=Konrad Königsberger |Titel=Analysis 1 |Datum=2004 |Seiten=1}}</ref>
# 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'')
# 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|mini|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>{{Literatur |Autor=Tilo Arens et al. |Titel=Mathematik |Auflage=5. |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2022 |ISBN=978-3-662-64388-4 |Seiten=84}}</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 ===
{{Hauptartikel|Gaußsche Summenformel}}
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 15a. {{Google Buch |BuchID=5cMjjJYMY_AC |Seite=89}}.</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 [[Reelle Zahl|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 ===
{{Hauptartikel|Pferde-Paradox}}
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 [[Latein|lat.]] ''inductio'', wörtlich „Hineinführung“. Der Zusatz ''vollständig'' signalisiert, dass es sich hier im Gegensatz zur [[Induktion (Philosophie)|Induktion]] im Sinne der Philosophie, die aus Spezialfällen ein allgemeines Gesetz erschließt und kein exaktes Schlussverfahren ist, um ein [[Deduktion|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>{{Literatur |Autor=Nachum L. Rabinovitch |Titel=Rabbi Levi Ben Gershon and the Origins of Mathematical Induction |Sammelwerk=Archive for History of Exact Sciences |Band=6 |Nummer=3 |Datum=1970 |Seiten=237–248}}</ref><ref>{{Literatur |Autor=[[Roshdi Rashed]] |Titel=L’induction mathématique: al-Karajī, as-Samaw'al |Sammelwerk=Archive for History of Exact Sciences |Band=9 |Nummer=1 |Datum=1972 |Seiten=1–21}}</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), {{Google Buch |BuchID=UqgUAAAAQAAJ |Hervorhebung="Traité du Triangle Arithmétique"}}.</ref> Zur Verbreitung von Induktionsbeweisen trug ab 1686 [[Jakob I Bernoulli]] wesentlich bei.<ref>{{Literatur |Autor= |Titel=Jakob Bernoulli |Sammelwerk=Lexikon bedeutender Mathematiker |Ort=Leipzig |Datum=1990 |ISBN=3-323-00319-5 |Seiten=48}}</ref>

Das Beweisverfahren wurde dann 1838 von [[Augustus De Morgan]] erstmals als ''Induktion'' oder ''sukzessive Induktion'' bezeichnet.<ref name="De Morgan">{{Literatur |Autor=Augustus De Morgan |Titel=Induction (Mathematics) |Sammelwerk=Penny Cyclopædia XII |Datum=1838 |Seiten=465–466}}</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">{{Literatur |Autor=Richard Dedekind |Titel=Was sind und was sollen die Zahlen? |Ort=Braunschweig |Datum=1888 |Fundstelle=§ 6 Satz 80}}</ref> Über dieses Werk aus der [[Mengenlehre#19. Jahrhundert|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 [[Peano-Axiome|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>{{Literatur |Autor=Giuseppe Peano |Hrsg=Fratres Bocca |Titel=Arithmetices principia nova methodo exposita |Ort=Rom / Florenz |Datum=1889}}</ref> Er zeigte mit formaler Strenge, dass aus seinen Zahlaxiomen, zu denen das Induktionsaxiom gehört, die ganze Arithmetik bis hin zu den [[Reelle Zahl|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
:# <math>A(0)</math> bzw. <math>A(1)</math> gilt und
:# 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 [[Ableitung (Logik)#Die Ableitbarkeitsrelation und der Ableitbarkeitsoperator|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-Axiome|Peano-Axiom]], dem ''Induktionsaxiom'', hergeleitet.<ref>{{Literatur |Autor=H. Wolter |Titel=Vollständige Induktion |Sammelwerk=Lexikon der Mathematik: Band 5: Sed bis Zyl |Auflage=2. |Verlag=Springer Spektrum |Ort=Berlin / Heidelberg |Datum=2017 |ISBN=978-3-662-53505-9 |Seiten=350}}</ref> Dieses lautet:

:Ist <math>\,K</math> eine Teilmenge der natürlichen Zahlen <math>\N</math> mit den Eigenschaften:
:# <math>\,1</math> ist ein Element von <math>\,K</math>
:# 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: [http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN23569441X&DMDID=dmdlog55 ''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 [[Ordinalzahl#Die natürlichen Zahlen als geordnete Mengen|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>{{Literatur |Autor=Forster, Lindemann |Titel=Analysis 1 |Datum=2023 |Seiten=1}}</ref>

# Im Induktionsanfang zeigt man, dass die Aussage für <math>n_0</math> gilt.
# 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 [[Fibonacci-Folge#Induktiver Beweis|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">{{Literatur |Autor=Schurz |Titel=Logik |Datum=2020 |Seiten=358}}</ref><ref>{{Literatur |Autor=Forster, Lindemann |Titel=Analysis 1 |Datum=2023 |Seiten=7}}</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">{{Literatur |Autor=Oliver Deiser |Titel=Einführung in die Mathematik 2.1 |Datum= |Seiten=271-272 |Online=https://www.aleph1.info/?call=Puc&permalink=ema21_Anh%C3%A4nge_5_Z1}}</ref> Trotz dieser prinzipiellen Gleichwertigkeit in der [[Beweistheorie|Beweisstärke]] ist der Unterschied in der [[Mathematische Logik|Ausdrucksstärke]] wegen der beliebig vielen Startwerte und der Möglichkeit des Rückgriffs auf beliebig viele Vorgänger groß, besonders bei [[Rekursionstheorie|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>{{Literatur |Autor=Augustin-Louis Cauchy |Titel=Cours d'analyse de l'école royale polytechnique. Première partie: Analyse algébrique |Ort=Paris |Datum=1821 |Seiten=457-459}}</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 [[Verallgemeinerte Fibonacci-Folge#Erweiterung auf alle ganzen Zahlen|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 [[Transfinite Induktion|transfiniter Induktion]].<ref>{{Literatur |Autor=Schurz |Titel=Logik |Datum=2020 |Seiten=350}}</ref>

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

== Rekursive oder induktive Definition ==
Die [[Rekursion|rekursive Definition]]<ref>{{Literatur |Autor=Königsberger |Titel=Analysis 1 |Datum=2004 |Seiten=2}}</ref> – auch ''induktive Definition'' genannt<ref name="Hausdorff">{{Literatur |Autor=Felix Hausdorff |Titel=Grundzüge der Mengenlehre |Verlag=Verlag von Veit & Comp. |Datum=1914 |Seiten=113 |Online=https://archive.org/details/grundzgedermen00hausuoft/page/112/mode/2up}}</ref><ref>{{Literatur |Autor=Ebbinghaus et al. |Titel=Zahlen |Auflage=3. |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1992 |ISBN=3-540-55654-0 |Seiten=15}}</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

# <math>x^1 := x</math> und
# 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
* {{Literatur
|Autor=Felix Göbler, Alex Küronya
|Titel=Vollständige Induktion
|Sammelwerk=Einstieg in die beweisorientierte Mathematik
|Verlag=Springer
|Ort=Berlin / Heidelberg
|Datum=2023
|ISBN=978-3-662-66355-4
|Seiten=95–109
|DOI=10.1007/978-3-662-66356-1_5}}
* 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 ==

{{Wikibooks|Mathe für Nicht-Freaks: Vollständige Induktion}}

* [https://www.w-i-g.de/index.php?title=Vollst%C3%A4ndige_Induktion Vollständige Induktion mit Beispielen.]
* [http://henked.de/begriffe/induktion.htm Vollständige Induktion.] henked.de
* [https://www.emath.de/Referate/induktion-aufgaben-loesungen.pdf emath.de] (PDF; 837 kB) Umfangreiche Aufgabensammlung zur vollständigen Induktion
* Joachim Mohr: [http://www.kilchb.de/vollstind.php Crashkurs in die vollständige Induktion.] kilchb.de
* [[Christian Spannagel]]: [https://av.tib.eu/search?q=vollst%C3%A4ndige+induktion&f=series%3Bhttp://av.tib.eu/resource/collection/233 Vorlesungen zur vollständigen Induktion].
* Beweise mit vollständiger Induktion auf Video anschaulich erklärt:
** {{YouTube |id=y8B8fl_usm0 |titel=Summe ungerader Zahlen (Satz des Maurolicus)}}.
** {{YouTube |id=7v1n8iJH5aY |titel=Gaußsche Summenformel |link=0}}.
** {{YouTube |id=qv2PDm2le_4 |titel=Bernoulli-Ungleichung |link=0}}.
** {{YouTube |id=aiWJwypx-Pk |titel=Beweis von 2n≥n2 |link=0}}.

== Einzelnachweise ==
<references />

{{Lesenswert|15. Juli 2010|76653225}}

{{Normdaten|TYP=s|GND=4124408-4|LCCN=sh85065806}}

{{SORTIERUNG:Vollstandige Induktion}}
[[:Kategorie:Mathematischer Grundbegriff]]
[[:Kategorie:Beweis (Mathematik)]]
[[:Kategorie:Wikipedia:Artikel mit Video]]

Vollständige Induktion - Versionsgeschichte

~2025-26902-00: /* Induktion mit beliebigem Anfang */ Überflüssiges Wort