Azərbaycan  AzərbaycanDeutschland  DeutschlandLietuva  LietuvaMalta  Maltaශ්‍රී ලංකාව  ශ්‍රී ලංකාවTürkmenistan  TürkmenistanTürkiyə  TürkiyəУкраина  Украина
Unterstützung
www.datawiki.de-de.nina.az
  • Heim

Die vollständige Induktion ist eine mathematische Beweismethode nach der eine Aussage für alle natürlichen Zahlen bewies

Vollständige Induktion

  • Startseite
  • Vollständige Induktion
Vollständige Induktion
www.datawiki.de-de.nina.azhttps://www.datawiki.de-de.nina.az

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann eine Herleitung nicht für jede Zahl einzeln erbracht werden. Sie ist ein deduktives Verfahren.

Der Beweis, dass die Aussage A⁡(n){\displaystyle \operatorname {A} (n)} für alle n≥n0{\displaystyle n\geq n_{0}} (n0{\displaystyle n_{0}} meist 1 oder 0) gilt, wird dabei in zwei Etappen durchgeführt:

  1. Im Induktionsanfang wird die Gültigkeit der Aussage A⁡(n0){\displaystyle \operatorname {A} (n_{0})} für eine kleinste Zahl n0{\displaystyle n_{0}} gezeigt.
  2. Im Induktionsschritt wird für ein beliebiges n≥n0{\displaystyle n\geq n_{0}} die Gültigkeit der Aussage A⁡(n+1){\displaystyle \operatorname {A} (n+1)} aus der Gültigkeit von A⁡(n){\displaystyle \operatorname {A} (n)} geschlussfolgert.

Oder weniger formal formuliert:

  1. Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt.
  2. Induktionsschritt: Folgendes wird bewiesen: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für deren Nachfolger.

Ausgehend vom Beweis für den Startwert erledigt der Induktionsschritt den Beweis für alle natürlichen Zahlen oberhalb des Startwertes.

Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik.

Aussageformen

Die vollständige Induktion befasst sich mit der Gültigkeit von Aussageformen A⁡(n){\displaystyle \operatorname {A} (n)}.

Beispiel (Siehe Gaußsche Summenformel):

A⁡(n):1+2+3+⋯+n=n⋅(n+1)2{\displaystyle \operatorname {A} (n):1+2+3+\dots +n={\tfrac {n\cdot (n+1)}{2}}} für n≥1{\displaystyle n\geq 1}

Wenn man Werte für n∈N{\displaystyle n\in \mathbb {N} } einsetzt, erhält man Aussagen, die wahr oder falsch sind.

A⁡(1):1=1⋅(1+1)2{\displaystyle \operatorname {A} (1):1={\tfrac {1\cdot (1+1)}{2}}}
A⁡(2):1+2=2⋅(2+1)2{\displaystyle \operatorname {A} (2):1+2={\tfrac {2\cdot (2+1)}{2}}}
A⁡(3):1+2+3=3⋅(3+1)2{\displaystyle \operatorname {A} (3):1+2+3={\tfrac {3\cdot (3+1)}{2}}}
⋮{\displaystyle \vdots }

Die Aussagen im obigen Beispiel sind offensichtlich alle wahr. Da man das nicht für alle (unendlich viele) Zahlen nachrechnen kann, bedarf es eines besonderen Beweisverfahrens. Dieses liefert die vollständige Induktion.

Die Aussageform A⁡(n){\displaystyle \operatorname {A} (n)} ist allgemeingültig, wenn sie für alle n∈N{\displaystyle n\in \mathbb {N} } wahr ist.

Um die Allgemeingültigkeit der Aussageform A⁡(n){\displaystyle \operatorname {A} (n)} zu beweisen, zeigt man Folgendes:

  1. A⁡(1){\displaystyle \operatorname {A} (1)} (Induktionsanfang) und
  2. aus der Aussage (der Induktionsannahme) A⁡(n){\displaystyle \operatorname {A} (n)} folgt stets die Aussage A⁡(n+1){\displaystyle \operatorname {A} (n+1)}, und zwar für alle n∈N{\displaystyle n\in \mathbb {N} }. (Das ist der Induktionsschritt.)

Veranschaulichung

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.

Die Allgemeingültigkeit einer Aussageform A⁡(n){\displaystyle \operatorname {A} (n)} ist für n=1,2,3,…{\displaystyle n=1,2,3,\ldots } bewiesen, wenn A⁡(1){\displaystyle \operatorname {A} (1)} gültig ist (der erste Stein fällt um) und wenn zusätzlich gilt A⁡(n)⇒A⁡(n+1){\displaystyle \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1)} für n=1,2,3,…{\displaystyle n=1,2,3,\ldots } (jeder Stein reißt beim Umfallen den nächsten Stein mit).

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 philosophischen Induktion, die aus Spezialfällen ein allgemeines Gesetz erschließt und kein exaktes Schlussverfahren ist, um ein anerkanntes deduktives Beweisverfahren handelt.

Das Induktionsprinzip steckt latent bereits in der von Euklid überlieferten pythagoreischen Zahlendefinition: „Zahl ist die aus Einheiten zusammengesetzte Menge.“ 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.

Lange galt ein Beweis von Franciscus Maurolicus von 1575 als älteste explizite vollständige Induktion (unten ausgeführt). 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. Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob I Bernoulli wesentlich bei.

Das Beweisverfahren wurde dann 1838 von Augustus De Morgan erstmals als Induktion oder sukzessive Induktion bezeichnet. 1888 prägte schließlich Richard Dedekind in seiner Schrift Was sind und was sollen die Zahlen? den Begriff vollständige Induktion. Ü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 das Beweisschema der vollständigen Induktion herleitbar ist. 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.

Definition

Seit Richard Dedekind ist die vollständige Induktion folgendermaßen festgelegt:

Um zu beweisen, dass eine Aussage für alle natürlichen Zahlen n≥n0{\displaystyle n\geq n_{0}} gilt, genügt es zu zeigen,
  • dass sie für n=n0{\displaystyle n=n_{0}} gilt und
  • dass aus der Gültigkeit der Aussage für eine Zahl n≥n0{\displaystyle n\geq n_{0}} stets auch ihre Gültigkeit für den Nachfolger n+1{\displaystyle n+1} folgt.

Als formale Schlussregel mit Ableitungsoperator ⊢{\displaystyle \vdash } lautet die vollständige Induktion für eine Aussage A⁡(n){\displaystyle \operatorname {A} (n)} und eine natürliche Zahl n0{\displaystyle n_{0}}:

A⁡(n0){\displaystyle \operatorname {A} (n_{0})} und ∀n∈N:(n≥n0∧A⁡(n)⇒A⁡(n+1)) ⊢ ∀n∈N:(n≥n0⇒A⁡(n)){\displaystyle \forall n\in \mathbb {N} \colon (n\geq n_{0}\land \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1))\ \vdash \ \forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n))}

Diese Schlussregel ist eine kompakte Formulierung des Beweisschemas der vollständigen Induktion, das didaktisch etwas ausführlicher formuliert werden kann:

Soll die Formel A⁡(n){\displaystyle \operatorname {A} (n)} für alle natürlichen Zahlen n≥n0{\displaystyle n\geq n_{0}} bewiesen werden, dann genügen dazu zwei Beweisschritte:
  1. der Induktionsanfang: der Beweis von A⁡(n0){\displaystyle \operatorname {A} (n_{0})},
  2. der Induktionsschritt (auch »Schluss von n{\displaystyle n} auf n+1{\displaystyle n+1}« genannt): der Beweis der Induktionsbehauptung A⁡(n+1){\displaystyle \operatorname {A} (n+1)} aus n≥n0{\displaystyle n\geq n_{0}} und der Induktionsvoraussetzung (auch Induktionsannahme, engl. induction hypothesis) A⁡(n){\displaystyle \operatorname {A} (n)}.
Nach obiger Schlussregel folgt dann die Verallgemeinerung der Formel A⁡(n){\displaystyle \operatorname {A} (n)} auf alle natürlichen Zahlen n≥n0{\displaystyle n\geq n_{0}} (der abschließende Induktionsschluss).

Die für natürliche Zahlen k∈K{\displaystyle k\in K} aus einer Menge K⊆N{\displaystyle K\subseteq \mathbb {N} } zu beweisende Aussage A⁡(k){\displaystyle \operatorname {A} (k)} tritt hierbei in mindestens drei Rollen auf:

(1) als Induktionsbehauptung für ein (einzelnes) beliebiges n∈K{\displaystyle n\in K}
(2) als Induktionsvoraussetzung für endlich viele kleinere natürliche Zahlen k∈K{\displaystyle k\in K}
(3) als zu beweisende allgemeine Aussage für alle (und damit für unendlich viele) n∈K{\displaystyle n\in K}

Meist ist n0=0{\displaystyle n_{0}=0} oder n0=1{\displaystyle n_{0}=1}. n0>1{\displaystyle n_{0}>1} ist jedoch möglich.

Denn da die Aussage A⁡(n){\displaystyle \operatorname {A} (n)} für n≥n0{\displaystyle n\geq n_{0}} gleichwertig ist zur Aussage B(n):=A(n+n0){\displaystyle B(n):=A(n+n_{0})} für n≥0{\displaystyle n\geq 0}, lässt sich Dedekinds Induktion auf die vollständige Induktion von 0 aus zurückführen:

B⁡(0),∀n∈N:(B⁡(n)⇒B⁡(n+1)) ⊢ ∀n∈N:B⁡(n)⇑⇑⇓A⁡(0+n0),∀n∈N:(A⁡(n+n0)⇒A⁡(n+1+n0)) A⁡(n+n0){\displaystyle {\begin{array}{llll}\operatorname {B} (0){,}&&&\forall n\in \mathbb {N} \colon (\operatorname {B} (n)&\Rightarrow \operatorname {B} (n+1))\ &&&\vdash \ \forall n\in \mathbb {N} \colon &\operatorname {B} (n)\\\Uparrow &&&&\Uparrow &&&&\Downarrow \\\operatorname {A} (0+n_{0}){,}&&&\forall n\in \mathbb {N} \colon (\operatorname {A} (n+n_{0})&\Rightarrow \operatorname {A} (n+1+n_{0}))\ &&&&\operatorname {A} (n+n_{0})\end{array}}}

Die Axiomatik der natürlichen Zahlen durch Peano

Peano bewies 1889 mit vollständiger Induktion die grundlegenden Rechenregeln für die Addition und Multiplikation: das Assoziativgesetz, Kommutativgesetz und Distributivgesetz.

Das Axiom der vollständigen Induktion

Die vollständige Induktion ist ein Axiom der natürlichen Zahlen. Meist wird sie jedoch aus dem gleichwertigen fünften Peano-Axiom, dem Induktionsaxiom, hergeleitet. Dieses lautet:

Ist K{\displaystyle \,K} eine Teilmenge der natürlichen Zahlen N{\displaystyle \mathbb {N} } mit den Eigenschaften:

  1. 1{\displaystyle \,1} ist ein Element von K{\displaystyle \,K}
  2. Mit n{\displaystyle \,n} aus K{\displaystyle \,K} ist stets auch n+1{\displaystyle \,n+1} aus K{\displaystyle \,K},

dann ist K=N{\displaystyle \,K=\mathbb {N} }.

Auch in anderen Konzepten der natürlichen Zahlen sind die Peano-Axiome und damit auch das Beweisverfahren 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
  • als frei von 1 erzeugtes Monoid, das von der Addition der Zahlen ausgeht
  • als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht
  • 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

Beispiele

Gaußsche Summenformel

→ Hauptartikel: Gaußsche Summenformel

Die Gaußsche Summenformel lautet:

    Für alle natürlichen Zahlen n≥1{\displaystyle n\geq 1} gilt die Aussage
    A⁡(n):⟺{\displaystyle \operatorname {A} (n):\Longleftrightarrow } 1+2+⋯+n{\displaystyle 1+2+\cdots +n} =n(n+1)2{\displaystyle ={\frac {n(n+1)}{2}}}.

Sie kann durch vollständige Induktion bewiesen werden.

Der Induktionsanfang ergibt sich unmittelbar:

    A⁡(1)⟺{\displaystyle \operatorname {A} (1)\Longleftrightarrow } 1{\displaystyle 1} =1(1+1)2{\displaystyle ={\frac {1(1+1)}{2}}}.

Im Induktionsschritt ist zu zeigen, dass für n≥1{\displaystyle n\geq 1} aus der Induktionsvoraussetzung

    A⁡(n)⟺{\displaystyle \operatorname {A} (n)\Longleftrightarrow } 1+2+⋯+n{\displaystyle 1+2+\cdots +n} =n(n+1)2{\displaystyle ={\frac {n(n+1)}{2}}}

die Induktionsbehauptung

    A⁡(n+1)⟺{\displaystyle \operatorname {A} (n\!+\!1)\Longleftrightarrow } 1+2+⋯+(n+1){\displaystyle 1+2+\cdots +(n\!+\!1)} =(n+1)((n+1)+1)2{\displaystyle ={\frac {(n\!+\!1){\bigl (}(n\!+\!1)+1{\bigr )}}{2}}}
=(n+1)(n+2)2{\displaystyle ={\frac {(n+1)(n+2)}{2}}}

(mit (n+1){\displaystyle (n\!+\!1)} an der Stelle des n{\displaystyle n} der Induktionsvoraussetzung) folgt.

Dies gelingt folgendermaßen:

1+2+⋯+n+(n+1){\displaystyle {\color {red}1+2+\cdots +n}+(n+1)} =n(n+1)2+(n+1){\displaystyle {\color {red}={\frac {n(n+1)}{2}}}+(n+1)} (rot markiert die Induktionsvoraussetzung)
=n(n+1)+2(n+1)2{\displaystyle ={\frac {n(n+1)+2(n+1)}{2}}} (Nach Ausklammern von (n+1){\displaystyle (n+1)} ergibt sich …)
=1+2+⋯+(n+1){\displaystyle =1+2+\cdots +(n\!+\!1)} =(n+1)(n+2)2{\displaystyle ={\frac {(n+1)(n+2)}{2}}} (… die Induktionsbehauptung A⁡(n+1){\displaystyle \operatorname {A} (n\!+\!1)} wie oben angegeben.)

Abschließend der Induktionsschluss:
    Damit ist die Aussage A⁡(n){\displaystyle \operatorname {A} (n)} für alle n≥1{\displaystyle n\geq 1} bewiesen.

Summe ungerader Zahlen (Maurolicus 1575)

Die schrittweise Berechnung der Summe der ersten n{\displaystyle n} ungeraden Zahlen legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von 1{\displaystyle 1} bis 2n−1{\displaystyle 2n-1} ist gleich dem Quadrat von n{\displaystyle n}:

1=1{\displaystyle 1=1}
1+3=4{\displaystyle 1+3=4}
1+3+5=9{\displaystyle 1+3+5=9}
1+3+5+7=16{\displaystyle 1+3+5+7=16}

Der zu beweisende allgemeine Satz lautet: ∑i=1n(2i−1)=n2{\displaystyle \textstyle \sum \limits _{i=1}^{n}(2i-1)=n^{2}}. Ihn bewies Maurolicus 1575 mit vollständiger Induktion. Ein Beweis mit heute geläufigen Rechenregeln liest sich folgendermaßen:

Der Induktionsanfang ∑i=11(2i−1)=12{\displaystyle \textstyle \sum \limits _{i=1}^{1}(2i-1)=1^{2}} mit n=1{\displaystyle n=1} ist wegen ∑i=11(2i−1)=2⋅1−1=1=12{\displaystyle \textstyle \sum \limits _{i=1}^{1}(2i-1)=2\cdot 1-1=1=1^{2}} leicht nachgeprüft.

Als Induktionsschritt ist zu zeigen: Wenn ∑i=1n(2i−1)=n2{\displaystyle \textstyle \sum \limits _{i=1}^{n}(2i-1)=n^{2}}, dann ∑i=1n+1(2i−1)=(n+1)2{\displaystyle \textstyle \sum \limits _{i=1}^{n+1}(2i-1)=(n+1)^{2}}. Er ergibt sich über folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:

∑i=1n+1(2i−1)=∑i=1n(2i−1)+(2(n+1)−1) = n2+2(n+1)−1=n2+2n+1=(n+1)2{\displaystyle {\begin{aligned}\sum _{i=1}^{n+1}(2i-1)\;&=\;\;{\color {red}\sum _{i=1}^{n}(2i-1)}+(2(n+1)-1)\\&\ {\color {red}=\;\;\ n^{2}}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}\end{aligned}}}
(Die Induktionsvoraussetzung ist rot markiert.)

Bernoullische Ungleichung

Die Bernoullische Ungleichung lautet für reelle Zahlen x{\displaystyle \,x} mit x≥−1{\displaystyle x\geq -1} und natürliche Zahlen n≥0{\displaystyle n\geq 0}

(1+x)n≥1+nx{\displaystyle (1+x)^{n}\geq 1+nx}.

Der Induktionsanfang mit n=0{\displaystyle n=0} gilt hier wegen (1+x)0=1≥1{\displaystyle (1+x)^{0}=1\geq 1} (wobei die Definitionslücke an der Stelle x=−1{\displaystyle x=-1} durch limx↘−1(1+x)0=1{\displaystyle \lim _{x\searrow -1}(1+x)^{0}=1} stetig ergänzt ist).

Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei obige Bedingung für x{\displaystyle \,x} dafür sorgt, dass der Term nicht negativ wird:

(1+x)n+1=(1+x)n⋅(1+x)≥(1+nx)⋅(1+x)=1+x+nx+nx2≥1+x+nx=1+(n+1)x.{\displaystyle {\begin{aligned}(1+x)^{n+1}&={\color {red}(1+x)^{n}}\cdot (1+x)\,\,{\color {red}\geq \;(1+nx)}\cdot (1+x)\\&=1+x+nx+nx^{2}\;\geq \;1+x+nx\\&=1+(n+1)x.\end{aligned}}}
(Die Induktionsvoraussetzung ist rot markiert.)

Das zweimalige Vorkommen des ≥{\displaystyle \geq }-Zeichens (in gleicher Richtung) lässt sich vereinfachen zu:

(1+x)n+1≥1+(n+1)x.{\displaystyle (1+x)^{n+1}\geq 1+(n+1)x.}

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 n{\displaystyle n} 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 n≥2{\displaystyle n\geq 2} benötigen, während der (fehlerhafte) Beweis die Induktion bei n=1{\displaystyle n=1} verankert und somit schon der Schritt von n=1{\displaystyle n=1} auf n=2{\displaystyle n=2} scheitert.

Induktionsvarianten

Induktion mit beliebigem Anfang

Induktionsbeweis der Ungleichung 2n≥n2{\displaystyle 2^{n}\geq n^{2}} für natürliche Zahlen n≥4{\displaystyle n\geq 4}:

Der Induktionsanfang für n=4{\displaystyle \,n=4} ergibt sich mit 24=16≥16=42{\displaystyle 2^{4}=16\geq 16=4^{2}}.
Der Induktionsschritt gilt aufgrund folgender Ableitung, die im zweiten Schritt die Induktionsvoraussetzung und im vierten und sechsten Schritt die Voraussetzung n≥4{\displaystyle n\geq 4} anwendet:
2n+1=2⋅2n≥2⋅n2=n2+n⋅n≥n2+4n=n2+2n+2n≥n2+2n+2⋅4≥n2+2n+1=(n+1)2.{\displaystyle {\begin{array}{lll}2^{n+1}&=2\cdot 2^{n}\geq 2\cdot n^{2}&=n^{2}+n\cdot n\geq n^{2}+4n\\&=n^{2}+2n+2n&\geq n^{2}+2n+2\cdot 4\\&\geq n^{2}+2n+1&=(n+1)^{2}.\end{array}}}

Die endlich vielen Fälle, die solch ein allgemeinerer Induktionsbeweis nicht abdeckt, können einzeln untersucht werden. Im Beispiel ist die Ungleichung für n=3{\displaystyle n=3} offenbar falsch.

Starke Induktion

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. Der Induktionsanfang ist dann für mehrere Startwerte durchzuführen. Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung für n{\displaystyle n} und n−1{\displaystyle n-1} nötig, dann ist ein Induktionsanfang für zwei aufeinander folgende Zahlen, also etwa 0 und 1, erforderlich. Als Induktionsvoraussetzung kann auch die Aussage für alle Zahlen zwischen dem Startwert und n{\displaystyle n} dienen. Ein Beispiel ist der Beweis, dass jede natürliche Zahl n≥2{\displaystyle n\geq 2} einen Primzahl-Teiler hat:

Induktionsanfang: 2 ist durch die Primzahl 2 teilbar.
Induktionsschritt: Die Aussage sei für alle m{\displaystyle m} mit 2≤m≤n{\displaystyle 2\leq m\leq n} erfüllt. Ist nun n+1{\displaystyle n+1} eine Primzahl, so ist n+1{\displaystyle n+1} selbst der gesuchte Teiler, und die Behauptung ist bewiesen. Ist n+1{\displaystyle \,n+1} keine Primzahl, so gibt es zwei Zahlen a,b∈N{\displaystyle a,b\in \mathbb {N} } mit a⋅b=n+1{\displaystyle a\cdot b=n+1} und 1<a<n+1{\displaystyle 1<a<n+1}. In diesem Fall besitzt a{\displaystyle a} gemäß Induktionsannahme (= Induktionsvoraussetzung) einen Primzahl-Teiler, etwa p{\displaystyle p}. Dann teilt p{\displaystyle p} auch n+1{\displaystyle n+1} und ist Primzahl-Teiler von n+1{\displaystyle n+1}. Damit ist auch für diesen zweiten Fall die Behauptung bewiesen.

Formale Definition

Die Aussage A⁡(n){\displaystyle \operatorname {A} (n)} ist für alle n≥n0{\displaystyle n\geq n_{0}} gültig, wenn Folgendes für jedes beliebige n≥n0{\displaystyle n\geq n_{0}} gilt:

(Induktionsschritt:) ⋀m=n0n−1A⁡(m)⟹A⁡(n){\displaystyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)\implies \operatorname {A} (n)} .

Das Beweisschema der starken Induktion besteht demgemäß nur aus dem Induktionsschritt.

Der Induktionsschritt ist also der Nachweis, dass
für jedes n≥n0{\displaystyle n\geq n_{0}}
die Induktionsvoraussetzung ⋀m=n0n−1A⁡(m){\displaystyle \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}              
die Induktionsbehauptung A⁡(n){\displaystyle \operatorname {A} (n)}   nach sich zieht.
Dann folgt die Verallgemeinerung
(der Induktionsschluss): Die Aussage A⁡(n){\displaystyle \operatorname {A} (n)} gilt für alle n≥n0{\displaystyle n\geq n_{0}}.

Induktionsanfänge, wie sie in der gewöhnlichen Induktion vorkommen, also bspw. der Nachweis der Aussage A⁡(n0){\displaystyle \operatorname {A} (n_{0})}, sind im Induktionsschritt enthalten. Es kann überdies vorkommen, dass mehr als eine Anfangsaussage vorab zu zeigen ist (siehe Fibonacci-Folge).

Offensichtlich folgt die (in der Einleitung formulierte) gewöhnliche vollständige Induktion aus der starken Induktion. Man kann aber auch die starke Induktion mit Hilfe der gewöhnlichen vollständigen Induktion beweisen.

Beweis  

Zu zeigen ist:

Wenn für alle n≥n0{\displaystyle n\geq n_{0}}
aus ⋀m=n0n−1A⁡(m){\displaystyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)} }{\displaystyle \left.{\begin{matrix}\\\\\\\\\end{matrix}}\right\rbrace } (Induktionsvoraussetzung gewöhnlich ⇒ stark)
A⁡(n){\displaystyle \operatorname {A} (n)} folgt,
dann gilt
A⁡(n){\displaystyle \operatorname {A} (n)} für alle n≥n0{\displaystyle n\geq n_{0}}. (Induktionsschluss gewöhnlich ⇒ stark)

Wir definieren die folgende Aussage B{\displaystyle \operatorname {B} } für natürliche Zahlen n∈N,n≥n0{\displaystyle n\in \mathbb {N} ,n\geq n_{0}}

B⁡(n):⟺⋀m=n0n−1A⁡(m){\displaystyle \operatorname {B} (n):\Longleftrightarrow \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}

und zeigen ihre Gültigkeit mittels gewöhnlicher vollständiger Induktion.

Induktionsanfang: Da B⁡(n0)⟺⋀m=n0n0−1A⁡(m)⟺⋀m∈∅A⁡(m){\displaystyle \operatorname {B} (n_{0})\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n_{0}-1}\operatorname {A} (m)\Longleftrightarrow \bigwedge _{m\in \emptyset }\operatorname {A} (m)}, die leere Und-Verknüpfung ist, gilt B⁡(n0){\displaystyle \operatorname {B} (n_{0})} gemäß Anmerkung sofort.

(Gewöhnlicher) Induktionsschritt von n{\displaystyle n} nach n+1{\displaystyle n+1}:

Sei n≥n0{\displaystyle n\geq n_{0}} beliebig und es gelte B⁡(n){\displaystyle \operatorname {B} (n)}, d. h. es gelte
⋀m=n0n−1A⁡(m){\displaystyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}.
Wegen der (Induktionsvoraussetzung gewöhnlich ⇒ stark) folgt daraus
A⁡(n){\displaystyle \operatorname {A} (n)}.
Zusammengenommen mit ⋀m=n0n−1A⁡(m){\displaystyle \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)} ergibt dies
⋀m=n0nA⁡(m){\displaystyle \bigwedge _{m=n_{0}}^{n}\operatorname {A} (m)}.

Damit haben wir B⁡(n+1){\displaystyle \operatorname {B} (n+1)} gezeigt, welches ⟺⋀m=n0nA⁡(m){\displaystyle \Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n}\operatorname {A} (m)} ist, und der gewöhnliche Induktionsschritt ist fertig. Wir schließen (gewöhnlicher Induktionsschluss):

Für alle n∈N,n≥n0{\displaystyle n\in \mathbb {N} ,n\geq n_{0}} gilt B⁡(n){\displaystyle \operatorname {B} (n)}.

Wegen B⁡(n)⟺⋀m=n0n−1A⁡(m){\displaystyle \operatorname {B} (n)\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)} ergibt sich a fortiori der starke Induktionsschluss:

Für alle n∈N,n≥n0{\displaystyle n\in \mathbb {N} ,n\geq n_{0}} gilt A⁡(n){\displaystyle \operatorname {A} (n)}.  ■

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. Das bedeutet aber keineswegs, dass letztere Definitionen nicht in gewöhnliche Rekursionen überführt werden können.

Beispiel
  • Die Folge (an)n∈N{\displaystyle \left(a_{n}\right)_{n\in \mathbb {N} }} sei definiert durch die Rekursionsformel
          an:=∑m=1n−1mam{\displaystyle a_{n}:=\sum _{m=1}^{n-1}ma_{m}}.
    Dann gilt:
          ∀n∈N:an=0{\displaystyle \forall n\in \mathbb {N} \colon a_{n}=0}.
    Der Beweis mittels starker Induktion ist trivial.
    Die Rekursion lässt sich jedoch auch unschwer in eine auf einen einzigen Vorgänger umformen:
          an=∑m=1n−2mam+(n−1)an−1=(1+(n−1))an−1{\displaystyle a_{n}=\sum _{m=1}^{n-2}ma_{m}+(n-1)\,a_{n-1}={\bigl (}1+(n-1){\bigr )}\,a_{n-1}}       (n≥2){\displaystyle (n\geq 2)}.

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 2k{\displaystyle 2^{k}} nach 2k+1{\displaystyle 2^{k+1}}) und die entstandenen Lücken nachträglich durch eine rückwärts gerichtete Herleitung von 2k{\displaystyle 2^{k}} nach n<2k{\displaystyle n<2^{k}} auf einen Schlag gefüllt werden.

Beispiel: Ungleichung vom arithmetischen und geometrischen Mittel

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 n{\displaystyle n} nach n+1{\displaystyle n+1}. Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von n{\displaystyle n} nach n−1{\displaystyle n-1} auszuführen. Beispielsweise lässt sich bei der Fibonacci-Folge die Rekursionsgleichung in die Gegenrichtung umstülpen.

Die vollständige Induktion ist von natürlichen Zahlen verallgemeinerbar auf Ordinalzahlen. Bei Ordinalzahlen, die größer als die natürlichen Zahlen sind, spricht man dann von transfiniter Induktion.

Die Induktion ist auch übertragbar 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 – auch induktive Definition genannt – ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird.

Beispiel einer rekursiven Funktion

f(n)={1fu¨r n=1n+f(n−1)fu¨r n>1{\displaystyle f(n)={\begin{cases}1&&\mathrm {f{\ddot {u}}r} \ n=1\\n+f(n-1)&&\mathrm {f{\ddot {u}}r} \ n>1\\\end{cases}}}

Mit Hilfe der vollständigen Induktion kann man beweisen (Gaußsche Summenformel):

f(n)=n(n+1)2{\displaystyle f(n)={\frac {n(n+1)}{2}}}

Die geschlossene Formel erspart die umständliche rekursive Berechnung.

Umgekehrt zeigt das nächste Beispiel, dass eine rekursive Berechnung günstiger sein kann.

Beispiel einer rekursiv definierten Funktion:

f(x,n)={{\displaystyle f(x,n)={\begin{cases}\\\\\\\\\end{cases}}} 1{\displaystyle 1} für   n=0{\displaystyle n=0},
x⋅f(x,n−1){\displaystyle x\cdot f(x,n-1)} für   n≥1{\displaystyle n\geq 1} und n{\displaystyle n} ungerade,
f(x2,n2){\displaystyle f\left(x^{2},{\tfrac {n}{2}}\right)} für   n≥2{\displaystyle n\geq 2} und n{\displaystyle n} gerade.

Man kann mit Hilfe der vollständigen Induktion nach n{\displaystyle n} zeigen, dass

f(x,n)=xn{\displaystyle f(x,n)=x^{n}}     für n≥0{\displaystyle n\geq 0} ist.

Der Vorteil dieser rekursiven Definition ist, dass man bei der Berechnung hoher Potenzen nicht n{\displaystyle n} Multiplikationen, sondern nur Multiplikationen in der Größenordnung von ln⁡(n){\displaystyle \ln(n)} hat. Sehr hohe Potenzen werden zum Beispiel bei der RSA-Verschlüsselung von Nachrichten verwendet.

Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten.

Literatur

  • Florian André Dalwigk: Vollständige Induktion. Springer, Berlin / Heidelberg 2019, ISBN 978-3-662-58632-7, doi:10.1007/978-3-662-58633-4. 
  • Felix Göbler, Alex Küronya: Vollständige Induktion. In: Einstieg in die beweisorientierte Mathematik. Springer, Berlin / Heidelberg 2023, ISBN 978-3-662-66355-4, S. 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.

Weblinks

Wikibooks: Mathe für Nicht-Freaks: Vollständige Induktion – Lern- und Lehrmaterialien
  • 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:
    • Summe ungerader Zahlen (Satz des Maurolicus) auf YouTube.
    • Gaußsche Summenformel auf YouTube.
    • Bernoulli-Ungleichung auf YouTube.
    • Beweis von 2n≥n2 auf YouTube.

Einzelnachweise

  1. Induktionsanfang und Induktionsschritt sind oft mit Methoden der „Schullogik“ herleitbar. Bei der vollständigen Induktion handelt es sich jedoch um ein Verfahren der Prädikatenlogik zweiter Stufe.
  2. Euklids Elemente VII, Definition 2. Dazu: Wilfried Neumaier: Antike Rhythmustheorien, Kap. 1 Antike mathematische Grundbegriffe, S. 11–12.
  3. Rabinovitch: Rabbi Levi Ben Gershon and the Origins of Mathematical Induction, in: Archive for History of Exact Sciences 6 (1970), S. 237–248.
  4. Roshdi Rashed: L’induction mathématique: al-Karajī, as-Samaw'al, in: Archive for History of Exact Sciences 9 (1972), S. 1–21.
  5. Maurolycus: Arithemticorum Liber primus, S. 7, Proposition 15a. eingeschränkte Vorschau in der Google-Buchsuche.
  6. Blaise Pascal: Traité du triangle arithmétique, S. 7, Conséquence douziesme, Le 1. (Induktionsanfang), Le 2. (Induktionsschritt), eingeschränkte Vorschau in der Google-Buchsuche.
  7. Lexikon bedeutender Mathematiker, Leipzig 1990, Artikel „Jakob Bernoulli“, S. 48.
  8. De Morgan: Artikel Induction (Mathematics) in: Penny Cyclopædia XII (1838), S. 465–466.
  9. Richard Dedekind: Was sind und was sollen die Zahlen?, Braunschweig 1888, § 6 Satz 80, Originalwortlaut: Satz der vollständigen Induktion (Schluss von n auf n’). Um zu beweisen, dass ein Satz für alle Zahlen n einer Kette m0 gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl n der Kette m0 stets seine Gültigkeit auch für die folgende Zahl n’ folgt.
  10. Peano: Arithmetices principia nova methodo exposita, 1889, in: G. Peano, Opere scelte II, Rom 1958, S. 20–55.
  11. Peano: Arithmetices principia nova methodo exposita. 1889. In: G. Peano: Opere scelte. Band II. Rom 1958. S. 35–36, 40–41.
  12. ausführliche Beweise auch in: Edmund Landau: Grundlagen der Analysis. Leipzig 1930.
  13. Felscher: Naive Mengen und abstrakte Zahlen I, S. 130–132.
  14. Dedekind: Was sind und was sollen die Zahlen?, § 6, Erklärung 71.
  15. dargestellt als Dedekind-Tripel in: Felscher: Naive Mengen und abstrakte Zahlen I, S. 147.
  16. S. Beweis der Formel von Binet für die Fibonacci-Folge
  17. Ein weiteres Beispiel ist der Beweis des Zeckendorf-Theorems; s. Der Satz von Zeckendorf.
  18. Definitionsgemäß ist ⋀m=n0n−1A⁡(m)=A⁡(n0)∧A⁡(n0+1)∧…∧A⁡(n−1){\displaystyle \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)\;=\;\operatorname {A} (n_{0})\wedge \operatorname {A} (n_{0}+1)\wedge \dotso \wedge \operatorname {A} (n-1)}.
    Die Induktionsvoraussetzung (die Induktionsannahme) besteht also darin, dass A⁡(m){\displaystyle \operatorname {A} (m)} für alle Zahlen m{\displaystyle m} von n0{\displaystyle n_{0}} bis n−1{\displaystyle n-1} als gültig angenommen wird.
  19. Da WAHR{\displaystyle {\mathsf {WAHR}}} das neutrale Element der Und-Verknüpfung ist und deshalb die leere Und-Verknüpfung ⋀m∈∅A⁡(m){\displaystyle \textstyle \bigwedge _{m\in \emptyset }\operatorname {A} (m)} den Wahrheitswert WAHR{\displaystyle {\mathsf {WAHR}}} hat, ist die Implikation (WAHR⟹A⁡(n0)){\displaystyle {\bigl (}{\mathsf {WAHR}}\implies \operatorname {A} (n_{0}){\bigr )}} durch das Zutreffen von A⁡(n0){\displaystyle \operatorname {A} (n_{0})} nachzuweisen. So betrachtet "steckt/stecken" der/die Induktionsanfang/anfänge bei der starken Induktion alle im Induktionsschritt.
  20. Oliver Deiser: Einführung in die Mathematik 2.1, S. 271/2 Der hauptsächliche Unterschied des starken Induktionsschemas zum gewöhnlichen ist – wie der Beweis zeigt, dass beim gewöhnlichen Schema jede Induktionsvoraussetzung genau einmal (in einer einzigen Induktionsstufe) benutzt wird, während beim starken Schema von mehreren höheren Induktionsstufen aus auf sie Bezug genommen werden kann.
  21. Cauchy, Augustin-Louis. Analyse algebrique. Paris 1821. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel ist dort auf Seite 457 ff.
  22. Eine Vorwärts-Rückwärts-Induktion ist auch der Beweis der jensenschen Ungleichung. Jensen: Sur les fonctions convexes et les inégalités entre les valeurs moyennes. In: Acta Math. 30, 1906, S. 175–193.
  23. Hausdorff: Grundzüge der Mengenlehre. 1914. S. 112–113 eingeschränkte Vorschau in der Google-Buchsuche.
  24. Peano: Le Definitione in Matematica. In: Opere scelte. Band II, 1921. S. 431, § 7 Definizioni per induzione.
  25. Zum Beispiel errechnet sich f(x,40){\displaystyle f(x,40)} =f(x2,20){\displaystyle =f(x^{2},20)} =f(x4,10){\displaystyle =f(x^{4},10)} =f(x8,5){\displaystyle =f(x^{8},5)} =x8⋅f(x8,4){\displaystyle =x^{8}\cdot f(x^{8},4)} =x8⋅f(x16,2){\displaystyle =x^{8}\cdot f(x^{16},2)} =x8⋅f(x32,1){\displaystyle =x^{8}\cdot f(x^{32},1)} =x8⋅x32{\displaystyle =x^{8}\cdot x^{32}} =x40{\displaystyle =x^{40}}
    für x=3 wird x40{\displaystyle x^{40}} wird in 6 Rechenschritten berechnet:
    1. x2=3⋅3=9{\displaystyle x^{2}=3\cdot 3=9}
    2. x4=9⋅9=81{\displaystyle x^{4}=9\cdot 9=81}
    3. x8=81⋅81={\displaystyle x^{8}=81\cdot 81=}6 561
    4. x16=6561⋅6561={\displaystyle x^{16}=6561\cdot 6561=}43 046 721
    5. x32=43046721⋅43046721={\displaystyle x^{32}=43046721\cdot 43046721=}1 853 020 188 851 841
    6. x40=6561⋅1853020188851841={\displaystyle x^{40}=6561\cdot 1853020188851841=}12 157 665 459 056 928 801
Dieser Artikel wurde am 15. Juli 2010 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.
Normdaten (Sachbegriff): GND: 4124408-4 (GND Explorer, lobid, OGND, AKS) | LCCN: sh85065806

Autor: www.NiNa.Az

Veröffentlichungsdatum: 16 Jul 2025 / 07:15

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele, Mobiltelefon, Mobil, Telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, komputer, Informationen zu Vollständige Induktion, Was ist Vollständige Induktion? Was bedeutet Vollständige Induktion?

Die vollstandige Induktion ist eine mathematische Beweismethode nach der eine Aussage fur alle naturlichen Zahlen bewiesen wird die grosser oder gleich einem bestimmten Startwert sind Da es sich um unendlich viele Zahlen handelt kann eine Herleitung nicht fur jede Zahl einzeln erbracht werden Sie ist ein deduktives Verfahren Der Beweis dass die Aussage A n displaystyle operatorname A n fur alle n n0 displaystyle n geq n 0 n0 displaystyle n 0 meist 1 oder 0 gilt wird dabei in zwei Etappen durchgefuhrt Im Induktionsanfang wird die Gultigkeit der Aussage A n0 displaystyle operatorname A n 0 fur eine kleinste Zahl n0 displaystyle n 0 gezeigt Im Induktionsschritt wird fur ein beliebiges n n0 displaystyle n geq n 0 die Gultigkeit der Aussage A n 1 displaystyle operatorname A n 1 aus der Gultigkeit von A n displaystyle operatorname A n geschlussfolgert Oder weniger formal formuliert Induktionsanfang Es wird bewiesen dass die Aussage fur die kleinste Zahl den Startwert gilt Induktionsschritt Folgendes wird bewiesen Gilt die Aussage fur eine beliebige Zahl so gilt sie auch fur deren Nachfolger Ausgehend vom Beweis fur den Startwert erledigt der Induktionsschritt den Beweis fur alle naturlichen Zahlen oberhalb des Startwertes Dieses Beweisverfahren ist von grundlegender Bedeutung fur die Arithmetik und Mengenlehre und damit fur alle Gebiete der Mathematik AussageformenDie vollstandige Induktion befasst sich mit der Gultigkeit von Aussageformen A n displaystyle operatorname A n Beispiel Siehe Gausssche Summenformel A n 1 2 3 n n n 1 2 displaystyle operatorname A n 1 2 3 dots n tfrac n cdot n 1 2 fur n 1 displaystyle n geq 1 Wenn man Werte fur n N displaystyle n in mathbb N einsetzt erhalt man Aussagen die wahr oder falsch sind A 1 1 1 1 1 2 displaystyle operatorname A 1 1 tfrac 1 cdot 1 1 2 A 2 1 2 2 2 1 2 displaystyle operatorname A 2 1 2 tfrac 2 cdot 2 1 2 A 3 1 2 3 3 3 1 2 displaystyle operatorname A 3 1 2 3 tfrac 3 cdot 3 1 2 displaystyle vdots Die Aussagen im obigen Beispiel sind offensichtlich alle wahr Da man das nicht fur alle unendlich viele Zahlen nachrechnen kann bedarf es eines besonderen Beweisverfahrens Dieses liefert die vollstandige Induktion Die Aussageform A n displaystyle operatorname A n ist allgemeingultig wenn sie fur alle n N displaystyle n in mathbb N wahr ist Um die Allgemeingultigkeit der Aussageform A n displaystyle operatorname A n zu beweisen zeigt man Folgendes A 1 displaystyle operatorname A 1 Induktionsanfang und aus der Aussage der Induktionsannahme A n displaystyle operatorname A n folgt stets die Aussage A n 1 displaystyle operatorname A n 1 und zwar fur alle n N displaystyle n in mathbb N Das ist der Induktionsschritt VeranschaulichungVollstandige Induktion als Dominoeffekt mit unendlich vielen Steinen Die Methode der vollstandigen Induktion ist mit dem Dominoeffekt vergleichbar Wenn der erste Dominostein fallt und durch jeden fallenden Dominostein der nachste umgestossen wird wird schliesslich jeder Dominostein der unendlich lang gedachten Kette irgendwann umfallen Die Allgemeingultigkeit einer Aussageform A n displaystyle operatorname A n ist fur n 1 2 3 displaystyle n 1 2 3 ldots bewiesen wenn A 1 displaystyle operatorname A 1 gultig ist der erste Stein fallt um und wenn zusatzlich gilt A n A n 1 displaystyle operatorname A n Rightarrow operatorname A n 1 fur n 1 2 3 displaystyle n 1 2 3 ldots jeder Stein reisst beim Umfallen den nachsten Stein mit Etymologie und GeschichteDie Bezeichnung Induktion leitet sich ab von lat inductio wortlich Hineinfuhrung Der Zusatz vollstandig signalisiert dass es sich hier im Gegensatz zur philosophischen Induktion die aus Spezialfallen ein allgemeines Gesetz erschliesst und kein exaktes Schlussverfahren ist um ein anerkanntes deduktives Beweisverfahren handelt Das Induktionsprinzip steckt latent bereits in der von Euklid uberlieferten pythagoreischen Zahlendefinition Zahl ist die aus Einheiten zusammengesetzte Menge Euklid fuhrte aber noch keine Induktionsbeweise sondern begnugte sich mit intuitiven exemplarischen Induktionen die sich aber vervollstandigen lassen Auch andere bedeutende Mathematiker der Antike und des Mittelalters hatten noch kein Bedurfnis nach prazisen Induktionsbeweisen Vereinzelte Ausnahmen im hebraischen und arabischen Sprachraum blieben ohne Nachfolge Lange galt ein Beweis von Franciscus Maurolicus von 1575 als alteste explizite vollstandige Induktion unten ausgefuhrt Er erorterte aber das allgemeine Beweisverfahren noch nicht Erst Blaise Pascal thematisierte das Induktionsprinzip mit Induktionsanfang und Induktionsschritt in seinem Traite du triangle arithmetique von 1654 Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob I Bernoulli wesentlich bei Das Beweisverfahren wurde dann 1838 von Augustus De Morgan erstmals als Induktion oder sukzessive Induktion bezeichnet 1888 pragte schliesslich Richard Dedekind in seiner Schrift Was sind und was sollen die Zahlen den Begriff vollstandige Induktion Uber dieses Werk aus der Grunderzeit der Mengenlehre wurde sie zum allgemein bekannten etablierten Beweisprinzip auf das seither kein Zweig der Mathematik mehr verzichten kann Ein Jahr spater 1889 formulierte Giuseppe Peano mit den Peanoschen Axiomen den ersten formalisierten Kalkul fur die naturlichen Zahlen mit einem Induktionsaxiom aus dem das Beweisschema der vollstandigen Induktion herleitbar ist Er zeigte mit formaler Strenge dass aus seinen Zahlaxiomen zu denen das Induktionsaxiom gehort die ganze Arithmetik bis hin zu den reellen Zahlen ableitbar ist Dadurch machte er die fundamentale Bedeutung und die Leistungskraft der Induktion voll bewusst DefinitionSeit Richard Dedekind ist die vollstandige Induktion folgendermassen festgelegt Um zu beweisen dass eine Aussage fur alle naturlichen Zahlen n n0 displaystyle n geq n 0 gilt genugt es zu zeigen dass sie fur n n0 displaystyle n n 0 gilt und dass aus der Gultigkeit der Aussage fur eine Zahl n n0 displaystyle n geq n 0 stets auch ihre Gultigkeit fur den Nachfolger n 1 displaystyle n 1 folgt Als formale Schlussregel mit Ableitungsoperator displaystyle vdash lautet die vollstandige Induktion fur eine Aussage A n displaystyle operatorname A n und eine naturliche Zahl n0 displaystyle n 0 A n0 displaystyle operatorname A n 0 und n N n n0 A n A n 1 n N n n0 A n displaystyle forall n in mathbb N colon n geq n 0 land operatorname A n Rightarrow operatorname A n 1 vdash forall n in mathbb N colon n geq n 0 Rightarrow operatorname A n Diese Schlussregel ist eine kompakte Formulierung des Beweisschemas der vollstandigen Induktion das didaktisch etwas ausfuhrlicher formuliert werden kann Soll die Formel A n displaystyle operatorname A n fur alle naturlichen Zahlen n n0 displaystyle n geq n 0 bewiesen werden dann genugen dazu zwei Beweisschritte der Induktionsanfang der Beweis von A n0 displaystyle operatorname A n 0 der Induktionsschritt auch Schluss von n displaystyle n auf n 1 displaystyle n 1 genannt der Beweis der Induktionsbehauptung A n 1 displaystyle operatorname A n 1 aus n n0 displaystyle n geq n 0 und der Induktionsvoraussetzung auch Induktionsannahme engl induction hypothesis A n displaystyle operatorname A n Nach obiger Schlussregel folgt dann die Verallgemeinerung der Formel A n displaystyle operatorname A n auf alle naturlichen Zahlen n n0 displaystyle n geq n 0 der abschliessende Induktionsschluss Die fur naturliche Zahlen k K displaystyle k in K aus einer Menge K N displaystyle K subseteq mathbb N zu beweisende Aussage A k displaystyle operatorname A k tritt hierbei in mindestens drei Rollen auf 1 als Induktionsbehauptung fur ein einzelnes beliebiges n K displaystyle n in K 2 als Induktionsvoraussetzung fur endlich viele kleinere naturliche Zahlen k K displaystyle k in K 3 als zu beweisende allgemeine Aussage fur alle und damit fur unendlich viele n K displaystyle n in K Meist ist n0 0 displaystyle n 0 0 oder n0 1 displaystyle n 0 1 n0 gt 1 displaystyle n 0 gt 1 ist jedoch moglich Denn da die Aussage A n displaystyle operatorname A n fur n n0 displaystyle n geq n 0 gleichwertig ist zur Aussage B n A n n0 displaystyle B n A n n 0 fur n 0 displaystyle n geq 0 lasst sich Dedekinds Induktion auf die vollstandige Induktion von 0 aus zuruckfuhren B 0 n N B n B n 1 n N B n A 0 n0 n N A n n0 A n 1 n0 A n n0 displaystyle begin array llll operatorname B 0 amp amp amp forall n in mathbb N colon operatorname B n amp Rightarrow operatorname B n 1 amp amp amp vdash forall n in mathbb N colon amp operatorname B n Uparrow amp amp amp amp Uparrow amp amp amp amp Downarrow operatorname A 0 n 0 amp amp amp forall n in mathbb N colon operatorname A n n 0 amp Rightarrow operatorname A n 1 n 0 amp amp amp amp operatorname A n n 0 end array Die Axiomatik der naturlichen Zahlen durch PeanoPeano bewies 1889 mit vollstandiger Induktion die grundlegenden Rechenregeln fur die Addition und Multiplikation das Assoziativgesetz Kommutativgesetz und Distributivgesetz Das Axiom der vollstandigen InduktionDie vollstandige Induktion ist ein Axiom der naturlichen Zahlen Meist wird sie jedoch aus dem gleichwertigen funften Peano Axiom dem Induktionsaxiom hergeleitet Dieses lautet Ist K displaystyle K eine Teilmenge der naturlichen Zahlen N displaystyle mathbb N mit den Eigenschaften 1 displaystyle 1 ist ein Element von K displaystyle K Mit n displaystyle n aus K displaystyle K ist stets auch n 1 displaystyle n 1 aus K displaystyle K dann ist K N displaystyle K mathbb N Auch in anderen Konzepten der naturlichen Zahlen sind die Peano Axiome und damit auch das Beweisverfahren der vollstandigen Induktion herleitbar zum Beispiel bei der Definition der naturlichen Zahlen als von 1 erzeugte geordnete Halbgruppe die der zitierten pythagoreischen Zahlendefinition entspricht als frei von 1 erzeugtes Monoid das von der Addition der Zahlen ausgeht als Algebra mit Nachfolger Abbildung die Dedekinds Zahlendefinition entspricht als kleinste induktive Menge namlich als kleinste Menge die das Unendlichkeitsaxiom erfullt wie es in der Mengenlehre ublich ist als Klasse der endlichen Ordinalzahlen die nur eine allgemeine Mengenlehre ohne Unendlichkeitsaxiom voraussetztBeispieleGausssche Summenformel Hauptartikel Gausssche Summenformel Die Gausssche Summenformel lautet Fur alle naturlichen Zahlen n 1 displaystyle n geq 1 gilt die Aussage A n displaystyle operatorname A n Longleftrightarrow 1 2 n displaystyle 1 2 cdots n n n 1 2 displaystyle frac n n 1 2 Sie kann durch vollstandige Induktion bewiesen werden Der Induktionsanfang ergibt sich unmittelbar A 1 displaystyle operatorname A 1 Longleftrightarrow 1 displaystyle 1 1 1 1 2 displaystyle frac 1 1 1 2 Im Induktionsschritt ist zu zeigen dass fur n 1 displaystyle n geq 1 aus der Induktionsvoraussetzung A n displaystyle operatorname A n Longleftrightarrow 1 2 n displaystyle 1 2 cdots n n n 1 2 displaystyle frac n n 1 2 die Induktionsbehauptung A n 1 displaystyle operatorname A n 1 Longleftrightarrow 1 2 n 1 displaystyle 1 2 cdots n 1 n 1 n 1 1 2 displaystyle frac n 1 bigl n 1 1 bigr 2 n 1 n 2 2 displaystyle frac n 1 n 2 2 mit n 1 displaystyle n 1 an der Stelle des n displaystyle n der Induktionsvoraussetzung folgt Dies gelingt folgendermassen 1 2 n n 1 displaystyle color red 1 2 cdots n n 1 n n 1 2 n 1 displaystyle color red frac n n 1 2 n 1 rot markiert die Induktionsvoraussetzung n n 1 2 n 1 2 displaystyle frac n n 1 2 n 1 2 Nach Ausklammern von n 1 displaystyle n 1 ergibt sich 1 2 n 1 displaystyle 1 2 cdots n 1 n 1 n 2 2 displaystyle frac n 1 n 2 2 die Induktionsbehauptung A n 1 displaystyle operatorname A n 1 wie oben angegeben Abschliessend der Induktionsschluss Damit ist die Aussage A n displaystyle operatorname A n fur alle n 1 displaystyle n geq 1 bewiesen Summe ungerader Zahlen Maurolicus 1575 Die schrittweise Berechnung der Summe der ersten n displaystyle n ungeraden Zahlen legt die Vermutung nahe Die Summe aller ungeraden Zahlen von 1 displaystyle 1 bis 2n 1 displaystyle 2n 1 ist gleich dem Quadrat von n displaystyle n 1 1 displaystyle 1 1 1 3 4 displaystyle 1 3 4 1 3 5 9 displaystyle 1 3 5 9 1 3 5 7 16 displaystyle 1 3 5 7 16 Der zu beweisende allgemeine Satz lautet i 1n 2i 1 n2 displaystyle textstyle sum limits i 1 n 2i 1 n 2 Ihn bewies Maurolicus 1575 mit vollstandiger Induktion Ein Beweis mit heute gelaufigen Rechenregeln liest sich folgendermassen Der Induktionsanfang i 11 2i 1 12 displaystyle textstyle sum limits i 1 1 2i 1 1 2 mit n 1 displaystyle n 1 ist wegen i 11 2i 1 2 1 1 1 12 displaystyle textstyle sum limits i 1 1 2i 1 2 cdot 1 1 1 1 2 leicht nachgepruft Als Induktionsschritt ist zu zeigen Wenn i 1n 2i 1 n2 displaystyle textstyle sum limits i 1 n 2i 1 n 2 dann i 1n 1 2i 1 n 1 2 displaystyle textstyle sum limits i 1 n 1 2i 1 n 1 2 Er ergibt sich uber folgende Gleichungskette bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird i 1n 1 2i 1 i 1n 2i 1 2 n 1 1 n2 2 n 1 1 n2 2n 1 n 1 2 displaystyle begin aligned sum i 1 n 1 2i 1 amp color red sum i 1 n 2i 1 2 n 1 1 amp color red n 2 2 n 1 1 n 2 2n 1 n 1 2 end aligned Die Induktionsvoraussetzung ist rot markiert Bernoullische Ungleichung Die Bernoullische Ungleichung lautet fur reelle Zahlen x displaystyle x mit x 1 displaystyle x geq 1 und naturliche Zahlen n 0 displaystyle n geq 0 1 x n 1 nx displaystyle 1 x n geq 1 nx Der Induktionsanfang mit n 0 displaystyle n 0 gilt hier wegen 1 x 0 1 1 displaystyle 1 x 0 1 geq 1 wobei die Definitionslucke an der Stelle x 1 displaystyle x 1 durch limx 1 1 x 0 1 displaystyle lim x searrow 1 1 x 0 1 stetig erganzt ist Den Induktionsschritt gewinnt man uber folgende Ableitung die im zweiten Schritt die Induktionsvoraussetzung verwendet wobei obige Bedingung fur x displaystyle x dafur sorgt dass der Term nicht negativ wird 1 x n 1 1 x n 1 x 1 nx 1 x 1 x nx nx2 1 x nx 1 n 1 x displaystyle begin aligned 1 x n 1 amp color red 1 x n cdot 1 x color red geq 1 nx cdot 1 x amp 1 x nx nx 2 geq 1 x nx amp 1 n 1 x end aligned Die Induktionsvoraussetzung ist rot markiert Das zweimalige Vorkommen des displaystyle geq Zeichens in gleicher Richtung lasst sich vereinfachen zu 1 x n 1 1 n 1 x displaystyle 1 x n 1 geq 1 n 1 x Pferde Paradox Hauptartikel Pferde Paradox Das Pferde Paradox ist ein Standardbeispiel fur eine fehlerhafte Anwendung der vollstandigen Induktion und illustriert die Bedeutung des Zusammenspiels von Induktionsverankerung und Induktionsschritt Bei ihm wird die unsinnige Aussage dass in einer Herde von n displaystyle n Pferden alle immer die gleiche Farbe besitzen anhand einer scheinbar korrekten Induktion bewiesen Dabei ist der Induktionsschritt selbst korrekt wurde aber die Induktionsverankerung bei einem n 2 displaystyle n geq 2 benotigen wahrend der fehlerhafte Beweis die Induktion bei n 1 displaystyle n 1 verankert und somit schon der Schritt von n 1 displaystyle n 1 auf n 2 displaystyle n 2 scheitert InduktionsvariantenInduktion mit beliebigem Anfang Induktionsbeweis der Ungleichung 2n n2 displaystyle 2 n geq n 2 fur naturliche Zahlen n 4 displaystyle n geq 4 Der Induktionsanfang fur n 4 displaystyle n 4 ergibt sich mit 24 16 16 42 displaystyle 2 4 16 geq 16 4 2 Der Induktionsschritt gilt aufgrund folgender Ableitung die im zweiten Schritt die Induktionsvoraussetzung und im vierten und sechsten Schritt die Voraussetzung n 4 displaystyle n geq 4 anwendet 2n 1 2 2n 2 n2 n2 n n n2 4n n2 2n 2n n2 2n 2 4 n2 2n 1 n 1 2 displaystyle begin array lll 2 n 1 amp 2 cdot 2 n geq 2 cdot n 2 amp n 2 n cdot n geq n 2 4n amp n 2 2n 2n amp geq n 2 2n 2 cdot 4 amp geq n 2 2n 1 amp n 1 2 end array dd Die endlich vielen Falle die solch ein allgemeinerer Induktionsbeweis nicht abdeckt konnen einzeln untersucht werden Im Beispiel ist die Ungleichung fur n 3 displaystyle n 3 offenbar falsch Starke Induktion Induktion mit mehreren Vorgangern In manchen Induktionsbeweisen kommt man in der Induktionsvoraussetzung mit dem Bezug auf einen einzigen Vorganger nicht aus bspw wenn eine Rekursionsformel mehrere Vorganger enthalt Der Induktionsanfang ist dann fur mehrere Startwerte durchzufuhren Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung fur n displaystyle n und n 1 displaystyle n 1 notig dann ist ein Induktionsanfang fur zwei aufeinander folgende Zahlen also etwa 0 und 1 erforderlich Als Induktionsvoraussetzung kann auch die Aussage fur alle Zahlen zwischen dem Startwert und n displaystyle n dienen Ein Beispiel ist der Beweis dass jede naturliche Zahl n 2 displaystyle n geq 2 einen Primzahl Teiler hat Induktionsanfang 2 ist durch die Primzahl 2 teilbar Induktionsschritt Die Aussage sei fur alle m displaystyle m mit 2 m n displaystyle 2 leq m leq n erfullt Ist nun n 1 displaystyle n 1 eine Primzahl so ist n 1 displaystyle n 1 selbst der gesuchte Teiler und die Behauptung ist bewiesen Ist n 1 displaystyle n 1 keine Primzahl so gibt es zwei Zahlen a b N displaystyle a b in mathbb N mit a b n 1 displaystyle a cdot b n 1 und 1 lt a lt n 1 displaystyle 1 lt a lt n 1 In diesem Fall besitzt a displaystyle a gemass Induktionsannahme Induktionsvoraussetzung einen Primzahl Teiler etwa p displaystyle p Dann teilt p displaystyle p auch n 1 displaystyle n 1 und ist Primzahl Teiler von n 1 displaystyle n 1 Damit ist auch fur diesen zweiten Fall die Behauptung bewiesen Formale Definition Die Aussage A n displaystyle operatorname A n ist fur alle n n0 displaystyle n geq n 0 gultig wenn Folgendes fur jedes beliebige n n0 displaystyle n geq n 0 gilt Induktionsschritt m n0n 1A m A n displaystyle bigwedge m n 0 n 1 operatorname A m implies operatorname A n Das Beweisschema der starken Induktion besteht demgemass nur aus dem Induktionsschritt Der Induktionsschritt ist also der Nachweis dassfur jedes n n0 displaystyle n geq n 0 die Induktionsvoraussetzung m n0n 1A m displaystyle textstyle bigwedge m n 0 n 1 operatorname A m die Induktionsbehauptung A n displaystyle operatorname A n nach sich zieht Dann folgt die Verallgemeinerung der Induktionsschluss Die Aussage A n displaystyle operatorname A n gilt fur alle n n0 displaystyle n geq n 0 Induktionsanfange wie sie in der gewohnlichen Induktion vorkommen also bspw der Nachweis der Aussage A n0 displaystyle operatorname A n 0 sind im Induktionsschritt enthalten Es kann uberdies vorkommen dass mehr als eine Anfangsaussage vorab zu zeigen ist siehe Fibonacci Folge Offensichtlich folgt die in der Einleitung formulierte gewohnliche vollstandige Induktion aus der starken Induktion Man kann aber auch die starke Induktion mit Hilfe der gewohnlichen vollstandigen Induktion beweisen Beweis Zu zeigen ist Wenn fur alle n n0 displaystyle n geq n 0 aus m n0n 1A m displaystyle bigwedge m n 0 n 1 operatorname A m displaystyle left begin matrix end matrix right rbrace Induktionsvoraussetzung gewohnlich stark A n displaystyle operatorname A n folgt dann giltA n displaystyle operatorname A n fur alle n n0 displaystyle n geq n 0 Induktionsschluss gewohnlich stark Wir definieren die folgende Aussage B displaystyle operatorname B fur naturliche Zahlen n N n n0 displaystyle n in mathbb N n geq n 0 B n m n0n 1A m displaystyle operatorname B n Longleftrightarrow bigwedge m n 0 n 1 operatorname A m und zeigen ihre Gultigkeit mittels gewohnlicher vollstandiger Induktion Induktionsanfang Da B n0 m n0n0 1A m m A m displaystyle operatorname B n 0 Longleftrightarrow textstyle bigwedge m n 0 n 0 1 operatorname A m Longleftrightarrow bigwedge m in emptyset operatorname A m die leere Und Verknupfung ist gilt B n0 displaystyle operatorname B n 0 gemass Anmerkung sofort Gewohnlicher Induktionsschritt von n displaystyle n nach n 1 displaystyle n 1 Sei n n0 displaystyle n geq n 0 beliebig und es gelte B n displaystyle operatorname B n d h es gelte m n0n 1A m displaystyle bigwedge m n 0 n 1 operatorname A m dd Wegen der Induktionsvoraussetzung gewohnlich stark folgt darausA n displaystyle operatorname A n dd Zusammengenommen mit m n0n 1A m displaystyle textstyle bigwedge m n 0 n 1 operatorname A m ergibt dies m n0nA m displaystyle bigwedge m n 0 n operatorname A m dd Damit haben wir B n 1 displaystyle operatorname B n 1 gezeigt welches m n0nA m displaystyle Longleftrightarrow textstyle bigwedge m n 0 n operatorname A m ist und der gewohnliche Induktionsschritt ist fertig Wir schliessen gewohnlicher Induktionsschluss Fur alle n N n n0 displaystyle n in mathbb N n geq n 0 gilt B n displaystyle operatorname B n Wegen B n m n0n 1A m displaystyle operatorname B n Longleftrightarrow textstyle bigwedge m n 0 n 1 operatorname A m ergibt sich a fortiori der starke Induktionsschluss Fur alle n N n n0 displaystyle n in mathbb N n geq n 0 gilt A n displaystyle operatorname A n Trotz dieser prinzipiellen Gleichwertigkeit in der Beweisstarke ist der Unterschied in der Ausdrucksstarke wegen der beliebig vielen Startwerte und der Moglichkeit des Ruckgriffs auf beliebig viele Vorganger gross besonders bei rekursiven Definitionen Das bedeutet aber keineswegs dass letztere Definitionen nicht in gewohnliche Rekursionen uberfuhrt werden konnen BeispielDie Folge an n N displaystyle left a n right n in mathbb N sei definiert durch die Rekursionsformel an m 1n 1mam displaystyle a n sum m 1 n 1 ma m Dann gilt n N an 0 displaystyle forall n in mathbb N colon a n 0 Der Beweis mittels starker Induktion ist trivial Die Rekursion lasst sich jedoch auch unschwer in eine auf einen einzigen Vorganger umformen an m 1n 2mam n 1 an 1 1 n 1 an 1 displaystyle a n sum m 1 n 2 ma m n 1 a n 1 bigl 1 n 1 bigr a n 1 n 2 displaystyle n geq 2 Induktion mit Vorwarts Ruckwarts Schritten Augustin Louis Cauchy fuhrte 1821 eine Induktionsvariante vor bei der der vorwarts gerichtete Induktionsschritt Sprunge macht namlich von 2k displaystyle 2 k nach 2k 1 displaystyle 2 k 1 und die entstandenen Lucken nachtraglich durch eine ruckwarts gerichtete Herleitung von 2k displaystyle 2 k nach n lt 2k displaystyle n lt 2 k auf einen Schlag gefullt werden Beispiel Ungleichung vom arithmetischen und geometrischen Mittel Weitere Induktionsvarianten Es gibt auch Sachlagen bei denen Aussagen uber alle ganzen Zahlen positive und negative mit vollstandiger Induktion bewiesen werden konnen Der Beweis in die positive Richtung geschieht wie gewohnt mit einem beliebigen Induktionsanfang und dem positiven Induktionsschritt von n displaystyle n nach n 1 displaystyle n 1 Danach kann es moglich sein den Induktionsschritt in die negative Richtung von n displaystyle n nach n 1 displaystyle n 1 auszufuhren Beispielsweise lasst sich bei der Fibonacci Folge die Rekursionsgleichung in die Gegenrichtung umstulpen Die vollstandige Induktion ist von naturlichen Zahlen verallgemeinerbar auf Ordinalzahlen Bei Ordinalzahlen die grosser als die naturlichen Zahlen sind spricht man dann von transfiniter Induktion Die Induktion ist auch ubertragbar auf sogenannte fundierte Mengen die eine der Zahlenordnung vergleichbare Ordnungsstruktur aufweisen hier spricht man zuweilen von struktureller Induktion Rekursive oder induktive DefinitionDie rekursive Definition auch induktive Definition genannt ist ein der vollstandigen Induktion analoges Verfahren bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird Beispiel einer rekursiven Funktion f n 1fu r n 1n f n 1 fu r n gt 1 displaystyle f n begin cases 1 amp amp mathrm f ddot u r n 1 n f n 1 amp amp mathrm f ddot u r n gt 1 end cases Mit Hilfe der vollstandigen Induktion kann man beweisen Gausssche Summenformel f n n n 1 2 displaystyle f n frac n n 1 2 Die geschlossene Formel erspart die umstandliche rekursive Berechnung Umgekehrt zeigt das nachste Beispiel dass eine rekursive Berechnung gunstiger sein kann Beispiel einer rekursiv definierten Funktion f x n displaystyle f x n begin cases end cases 1 displaystyle 1 fur n 0 displaystyle n 0 x f x n 1 displaystyle x cdot f x n 1 fur n 1 displaystyle n geq 1 und n displaystyle n ungerade f x2 n2 displaystyle f left x 2 tfrac n 2 right fur n 2 displaystyle n geq 2 und n displaystyle n gerade Man kann mit Hilfe der vollstandigen Induktion nach n displaystyle n zeigen dass f x n xn displaystyle f x n x n fur n 0 displaystyle n geq 0 ist Der Vorteil dieser rekursiven Definition ist dass man bei der Berechnung hoher Potenzen nicht n displaystyle n Multiplikationen sondern nur Multiplikationen in der Grossenordnung von ln n displaystyle ln n hat Sehr hohe Potenzen werden zum Beispiel bei der RSA Verschlusselung von Nachrichten verwendet Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten LiteraturFlorian Andre Dalwigk Vollstandige Induktion Springer Berlin Heidelberg 2019 ISBN 978 3 662 58632 7 doi 10 1007 978 3 662 58633 4 Felix Gobler Alex Kuronya Vollstandige Induktion In Einstieg in die beweisorientierte Mathematik Springer Berlin Heidelberg 2023 ISBN 978 3 662 66355 4 S 95 109 doi 10 1007 978 3 662 66356 1 5 Ilja S Sominski Die Methode der vollstandigen Induktion Kleine Erganzungsreihe zu den Hochschulbuchern Mathematik Band 3 10 Auflage VEB Deutscher Verlag der Wissenschaften Berlin 1971 WeblinksWikibooks Mathe fur Nicht Freaks Vollstandige Induktion Lern und Lehrmaterialien Vollstandige Induktion mit Beispielen Vollstandige Induktion henked de emath de PDF 837 kB Umfangreiche Aufgabensammlung zur vollstandigen Induktion Joachim Mohr Crashkurs in die vollstandige Induktion kilchb de Christian Spannagel Vorlesungen zur vollstandigen Induktion Beweise mit vollstandiger Induktion auf Video anschaulich erklart Summe ungerader Zahlen Satz des Maurolicus auf YouTube Gausssche Summenformel auf YouTube Bernoulli Ungleichung auf YouTube Beweis von 2n n2 auf YouTube EinzelnachweiseInduktionsanfang und Induktionsschritt sind oft mit Methoden der Schullogik herleitbar Bei der vollstandigen Induktion handelt es sich jedoch um ein Verfahren der Pradikatenlogik zweiter Stufe Euklids Elemente VII Definition 2 Dazu Wilfried Neumaier Antike Rhythmustheorien Kap 1 Antike mathematische Grundbegriffe S 11 12 Rabinovitch Rabbi Levi Ben Gershon and the Origins of Mathematical Induction in Archive for History of Exact Sciences 6 1970 S 237 248 Roshdi Rashed L induction mathematique al Karaji as Samaw al in Archive for History of Exact Sciences 9 1972 S 1 21 Maurolycus Arithemticorum Liber primus S 7 Proposition 15a eingeschrankte Vorschau in der Google Buchsuche Blaise Pascal Traite du triangle arithmetique S 7 Consequence douziesme Le 1 Induktionsanfang Le 2 Induktionsschritt eingeschrankte Vorschau in der Google Buchsuche Lexikon bedeutender Mathematiker Leipzig 1990 Artikel Jakob Bernoulli S 48 De Morgan Artikel Induction Mathematics in Penny Cyclopaedia XII 1838 S 465 466 Richard Dedekind Was sind und was sollen die Zahlen Braunschweig 1888 6 Satz 80 Originalwortlaut Satz der vollstandigen Induktion Schluss von n auf n Um zu beweisen dass ein Satz fur alle Zahlen n einer Kette m0 gilt genugt es zu zeigen dass er fur n m gilt und dass aus der Gultigkeit des Satzes fur eine Zahl n der Kette m0 stets seine Gultigkeit auch fur die folgende Zahl n folgt Peano Arithmetices principia nova methodo exposita 1889 in G Peano Opere scelte II Rom 1958 S 20 55 Peano Arithmetices principia nova methodo exposita 1889 In G Peano Opere scelte Band II Rom 1958 S 35 36 40 41 ausfuhrliche Beweise auch in Edmund Landau Grundlagen der Analysis Leipzig 1930 Felscher Naive Mengen und abstrakte Zahlen I S 130 132 Dedekind Was sind und was sollen die Zahlen 6 Erklarung 71 dargestellt als Dedekind Tripel in Felscher Naive Mengen und abstrakte Zahlen I S 147 S Beweis der Formel von Binet fur die Fibonacci Folge Ein weiteres Beispiel ist der Beweis des Zeckendorf Theorems s Der Satz von Zeckendorf Definitionsgemass ist m n0n 1A m A n0 A n0 1 A n 1 displaystyle textstyle bigwedge m n 0 n 1 operatorname A m operatorname A n 0 wedge operatorname A n 0 1 wedge dotso wedge operatorname A n 1 Die Induktionsvoraussetzung die Induktionsannahme besteht also darin dass A m displaystyle operatorname A m fur alle Zahlen m displaystyle m von n0 displaystyle n 0 bis n 1 displaystyle n 1 als gultig angenommen wird Da WAHR displaystyle mathsf WAHR das neutrale Element der Und Verknupfung ist und deshalb die leere Und Verknupfung m A m displaystyle textstyle bigwedge m in emptyset operatorname A m den Wahrheitswert WAHR displaystyle mathsf WAHR hat ist die Implikation WAHR A n0 displaystyle bigl mathsf WAHR implies operatorname A n 0 bigr durch das Zutreffen von A n0 displaystyle operatorname A n 0 nachzuweisen So betrachtet steckt stecken der die Induktionsanfang anfange bei der starken Induktion alle im Induktionsschritt Oliver Deiser Einfuhrung in die Mathematik 2 1 S 271 2 Der hauptsachliche Unterschied des starken Induktionsschemas zum gewohnlichen ist wie der Beweis zeigt dass beim gewohnlichen Schema jede Induktionsvoraussetzung genau einmal in einer einzigen Induktionsstufe benutzt wird wahrend beim starken Schema von mehreren hoheren Induktionsstufen aus auf sie Bezug genommen werden kann Cauchy Augustin Louis Analyse algebrique Paris 1821 Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel ist dort auf Seite 457 ff Eine Vorwarts Ruckwarts Induktion ist auch der Beweis der jensenschen Ungleichung Jensen Sur les fonctions convexes et les inegalites entre les valeurs moyennes In Acta Math 30 1906 S 175 193 Hausdorff Grundzuge der Mengenlehre 1914 S 112 113 eingeschrankte Vorschau in der Google Buchsuche Peano Le Definitione in Matematica In Opere scelte Band II 1921 S 431 7 Definizioni per induzione Zum Beispiel errechnet sich f x 40 displaystyle f x 40 f x2 20 displaystyle f x 2 20 f x4 10 displaystyle f x 4 10 f x8 5 displaystyle f x 8 5 x8 f x8 4 displaystyle x 8 cdot f x 8 4 x8 f x16 2 displaystyle x 8 cdot f x 16 2 x8 f x32 1 displaystyle x 8 cdot f x 32 1 x8 x32 displaystyle x 8 cdot x 32 x40 displaystyle x 40 fur x 3 wird x40 displaystyle x 40 wird in 6 Rechenschritten berechnet 1 x2 3 3 9 displaystyle x 2 3 cdot 3 9 2 x4 9 9 81 displaystyle x 4 9 cdot 9 81 3 x8 81 81 displaystyle x 8 81 cdot 81 6 561 4 x16 6561 6561 displaystyle x 16 6561 cdot 6561 43 046 721 5 x32 43046721 43046721 displaystyle x 32 43046721 cdot 43046721 1 853 020 188 851 841 6 x40 6561 1853020188851841 displaystyle x 40 6561 cdot 1853020188851841 12 157 665 459 056 928 801Dieser Artikel wurde am 15 Juli 2010 in dieser Version in die Liste der lesenswerten Artikel aufgenommen Normdaten Sachbegriff GND 4124408 4 GND Explorer lobid OGND AKS LCCN sh85065806

Neueste Artikel
  • Juli 18, 2025

    Amt Scheßlitz

  • Juli 18, 2025

    Amt Schenkendöbern

  • Juli 18, 2025

    Amt Salmünster

  • Juli 18, 2025

    Amt Rüstringen

  • Juli 18, 2025

    Amt Köpenick

www.NiNa.Az - Studio

    Kontaktieren Sie uns
    Sprachen
    Kontaktieren Sie uns
    DMCA Sitemap
    © 2019 nina.az - Alle Rechte vorbehalten.
    Copyright: Dadash Mammadov
    Eine kostenlose Website, die Daten- und Dateiaustausch aus der ganzen Welt ermöglicht.
    Spi.