Vollständige Induktion – Wikipedia

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.

Der Beweis, dass die Aussage

${displaystyle operatorname {A} (n)}$

für alle

${displaystyle ngeq n_{0}}$

(

${displaystyle n_{0}}$

meist 1 oder 0) gilt,
wird daher in zwei Etappen durchgeführt:

1. Im Induktionsanfang wird die Aussage
   ${displaystyle operatorname {A} (n_{0})}$

   für eine kleinste Zahl

   ${displaystyle n_{0}}$

   hergeleitet.

2. Im Induktionsschritt wird für ein beliebiges
   ${displaystyle ngeq n_{0}}$

   die Aussage

   ${displaystyle operatorname {A} (n+1)}$

   aus der Aussage

   ${displaystyle operatorname {A} (n)}$

   hergeleitet.

Oder weniger „mathematisch“ 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 die Zahl eins größer.

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.

Die vollständige Induktion befasst sich mit der Gültigkeit von Aussageformen

${displaystyle operatorname {A} (n)}$

.

Beispiel (Siehe Gaußsche Summenformel):

${displaystyle operatorname {A} (n):1+2+3+dots +n={tfrac {ncdot (n+1)}{2}}}$

für

${displaystyle ngeq 1}$

Wenn man Werte für

${displaystyle nin mathbb {N} }$

einsetzt, erhält man Aussagen, die wahr oder falsch sind.

${displaystyle operatorname {A} (1):1={tfrac {1cdot (1+1)}{2}}}$

${displaystyle operatorname {A} (2):1+2={tfrac {2cdot (2+1)}{2}}}$

${displaystyle operatorname {A} (3):1+2+3={tfrac {3cdot (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

${displaystyle operatorname {A} (n)}$

ist allgemeingültig, wenn sie für alle

${displaystyle nin mathbb {N} }$

wahr ist.

Um die Allgemeingültigkeit der Aussageform

${displaystyle operatorname {A} (n)}$

zu beweisen, zeigt man Folgendes:

1. 
   ${displaystyle operatorname {A} (1)}$

   (Induktionsanfang) und

2. aus der Aussage (der Induktionsannahme)
   ${displaystyle operatorname {A} (n)}$

   folgt stets die Aussage

   ${displaystyle operatorname {A} (n+1)}$

   , und zwar für alle

   ${displaystyle nin mathbb {N} }$

   . (Das ist der Induktionsschritt.)^[1]

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

${displaystyle operatorname {A} (n)}$

ist für

${displaystyle n=1,2,3,ldots }$

bewiesen, wenn

${displaystyle operatorname {A} (1)}$

gültig ist (der erste Stein fällt um) und wenn zusätzlich gilt

${displaystyle operatorname {A} (n)Rightarrow operatorname {A} (n+1)}$

für

${displaystyle n=1,2,3,ldots }$

(jeder Stein reißt beim Umfallen den nächsten Stein mit).

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

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

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

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

Um zu beweisen, dass ein Satz für alle natürlichen Zahlen

${displaystyle ngeq n_{0}}$

gilt, genügt es zu zeigen,

• dass er für
  ${displaystyle n=n_{0}}$

  gilt und

• dass aus der Gültigkeit des Satzes für eine Zahl
  ${displaystyle ngeq n_{0}}$

  stets seine Gültigkeit auch für die folgende Zahl

  ${displaystyle n+1}$

  folgt.^[9]

Als formale Schlussregel mit Ableitungsoperator

${displaystyle vdash }$

lautet die vollständige Induktion für eine Aussage

${displaystyle operatorname {A} (n)}$

und eine natürliche Zahl

${displaystyle n_{0}}$

:

${displaystyle operatorname {A} (n_{0})}$

und

${displaystyle forall nin mathbb {N} colon (ngeq n_{0}land operatorname {A} (n)Rightarrow operatorname {A} (n+1)) vdash forall nin mathbb {N} colon (ngeq 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

${displaystyle operatorname {A} (n)}$

für alle natürlichen Zahlen

${displaystyle ngeq n_{0}}$

bewiesen werden, dann genügen dazu zwei schritte:

1. der Induktionsanfang: der von
   ${displaystyle operatorname {A} (n_{0})}$

   ,

2. der Induktionsschritt (auch »Schluss von
   ${displaystyle n}$

   auf

   ${displaystyle n+1}$

   «^[9] genannt): der der Induktionsbehauptung

   ${displaystyle operatorname {A} (n+1)}$

   aus

   ${displaystyle ngeq n_{0}}$

   und der Induktionsvoraussetzung (auch Induktionsannahme, engl. induction hypothesis)

   ${displaystyle operatorname {A} (n)}$

   .

Nach obiger Schlussregel folgt dann die Verallgemeinerung der Formel

${displaystyle operatorname {A} (n)}$

auf alle natürlichen Zahlen

${displaystyle ngeq n_{0}}$

(der abschließende Induktionsschluss).

Die für natürliche Zahlen

${displaystyle kin K}$

aus einer Menge

${displaystyle Ksubseteq mathbb {N} }$

zu beweisende Aussage

${displaystyle operatorname {A} (k)}$

tritt hierbei in mindestens 3 Rollen auf:

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

---

Meist ist

${displaystyle n_{0}=0}$

oder

${displaystyle n_{0}=1}$

.

${displaystyle n_{0}>1}$

${displaystyle operatorname {A} (n)}$

für

${displaystyle ngeq n_{0}}$

gleichwertig ist zur Aussage

${displaystyle B(n):=A(n+n_{0})}$

für

${displaystyle ngeq 0}$

, lässt sich Dedekinds Induktion auf die vollständige Induktion von 0 aus zurückführen:

${displaystyle {begin{array}{llll}operatorname {B} (0){,}&&&forall nin mathbb {N} colon (operatorname {B} (n)&Rightarrow operatorname {B} (n+1)) &&&vdash forall nin mathbb {N} colon &operatorname {B} (n)\Uparrow &&&&Uparrow &&&&Downarrow \operatorname {A} (0+n_{0}){,}&&&forall nin mathbb {N} colon (operatorname {A} (n+n_{0})&Rightarrow operatorname {A} (n+1+n_{0})) &&&&operatorname {A} (n+n_{0})end{array}}}$

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

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

${displaystyle ,K}$

eine Teilmenge der natürlichen Zahlen

${displaystyle mathbb {N} }$

mit den Eigenschaften:

1. 
   ${displaystyle ,1}$

   ist ein Element von

   ${displaystyle ,K}$

   

2. Mit
   ${displaystyle ,n}$

   aus

   ${displaystyle ,K}$

   ist stets auch

   ${displaystyle ,n+1}$

   aus

   ${displaystyle ,K}$

   ,

dann ist

${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^[2]
• als frei von 1 erzeugtes Monoid, das von der Addition der Zahlen ausgeht^[13]
• als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht^[14][15]
• 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

Gaußsche Summenformel[Bearbeiten | Quelltext bearbeiten]

Die Gaußsche Summenformel lautet:

Für alle natürlichen Zahlen ${displaystyle ngeq 1}$ gilt die Aussage
${displaystyle operatorname {A} (n):Longleftrightarrow }$	${displaystyle 1+2+cdots +n}$	${displaystyle ={frac {n(n+1)}{2}}}$ .

Sie kann durch vollständige Induktion bewiesen werden.

Der Induktionsanfang ergibt sich unmittelbar:

${displaystyle operatorname {A} (1)Longleftrightarrow }$

${displaystyle 1}$

${displaystyle ={frac {1(1+1)}{2}}}$ .

Im Induktionsschritt ist zu zeigen, dass für

${displaystyle ngeq 1}$

aus der Induktionsvoraussetzung

${displaystyle operatorname {A} (n)Longleftrightarrow }$

${displaystyle 1+2+cdots +n}$

${displaystyle ={frac {n(n+1)}{2}}}$

die Induktionsbehauptung

${displaystyle operatorname {A} (n!+!1)Longleftrightarrow }$	${displaystyle 1+2+cdots +(n!+!1)}$	${displaystyle ={frac {(n!+!1){bigl (}(n!+!1)+1{bigr )}}{2}}}$
		${displaystyle ={frac {(n+1)(n+2)}{2}}}$

(mit

${displaystyle (n!+!1)}$

an der Stelle des

${displaystyle n}$

der Induktionsvoraussetzung) folgt.

Dies gelingt folgendermaßen:

Abschließend der Induktionsschluss:
    Damit ist die Aussage

${displaystyle operatorname {A} (n)}$

für alle

${displaystyle ngeq 1}$

bewiesen.

Summe ungerader Zahlen (Maurolicus 1575)[Bearbeiten | Quelltext bearbeiten]

Die schrittweise Berechnung der Summe der ersten

${displaystyle n}$

ungeraden Zahlen legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von

${displaystyle 1}$

bis

${displaystyle 2n-1}$

ist gleich dem Quadrat von

${displaystyle n}$

:

${displaystyle 1=1}$

${displaystyle 1+3=4}$

${displaystyle 1+3+5=9}$

${displaystyle 1+3+5+7=16}$

Der zu beweisende allgemeine Satz lautet:

${displaystyle textstyle sum limits _{i=1}^{n}(2i-1)=n^{2}}$

. Ihn bewies Maurolicus 1575 mit vollständiger Induktion.^[5] Ein Beweis mit heute geläufigen Rechenregeln liest sich folgendermaßen:

Der Induktionsanfang

${displaystyle textstyle sum limits _{i=1}^{1}(2i-1)=1^{2}}$

mit

${displaystyle n=1}$

ist wegen

${displaystyle textstyle sum limits _{i=1}^{1}(2i-1)=2cdot 1-1=1=1^{2}}$

leicht nachgeprüft.

Als Induktionsschritt ist zu zeigen: Wenn

${displaystyle textstyle sum limits _{i=1}^{n}(2i-1)=n^{2}}$

, dann

${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:

${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[Bearbeiten | Quelltext bearbeiten]

Die Bernoullische Ungleichung lautet für reelle Zahlen

${displaystyle ,x}$

mit

${displaystyle xgeq -1}$

und natürliche Zahlen

${displaystyle ngeq 0}$

${displaystyle (1+x)^{n}geq 1+nx}$

.

Der Induktionsanfang mit

${displaystyle n=0}$

gilt hier wegen

${displaystyle (1+x)^{0}=1geq 1}$

(wobei die Definitionslücke an der Stelle

${displaystyle x=-1}$

durch

${displaystyle lim _{xsearrow -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

${displaystyle ,x}$

dafür sorgt, dass der Term nicht negativ wird:

${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:

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

Pferde-Paradox[Bearbeiten | Quelltext bearbeiten]

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

${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

${displaystyle ngeq 2}$

benötigen, während der (fehlerhafte) Beweis die Induktion bei

${displaystyle n=1}$

verankert und somit schon der Schritt von

${displaystyle n=1}$

auf

${displaystyle n=2}$

scheitert.

Induktion mit beliebigem Anfang[Bearbeiten | Quelltext bearbeiten]

Induktionsbeweis der Ungleichung

${displaystyle 2^{n}geq n^{2}}$

für natürliche Zahlen

${displaystyle ngeq 4}$

:

Der Induktionsanfang für

${displaystyle ,n=4}$

ergibt sich mit

${displaystyle 2^{4}=16geq 16=4^{2}}$

.

Der Induktionsschritt gilt aufgrund folgender Ableitung, die im zweiten Schritt die Induktionsvoraussetzung und im vierten und sechsten Schritt die Voraussetzung

${displaystyle ngeq 4}$

anwendet:

${displaystyle {begin{array}{lll}2^{n+1}&=2cdot 2^{n}geq 2cdot n^{2}&=n^{2}+ncdot ngeq n^{2}+4n\&=n^{2}+2n+2n&geq n^{2}+2n+2cdot 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

${displaystyle n=3}$

offenbar falsch.

Starke Induktion[Bearbeiten | Quelltext bearbeiten]

Induktion mit mehreren Vorgängern[Bearbeiten | Quelltext bearbeiten]

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.^[16]
Der Induktionsanfang ist dann für mehrere Startwerte durchzuführen.
Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung für

${displaystyle n}$

und

${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

${displaystyle n}$

dienen. Ein Beispiel^[17] ist der Beweis, dass jede natürliche Zahl

${displaystyle ngeq 2}$

einen Primzahl-Teiler hat:

Induktionsanfang: 2 ist durch die Primzahl 2 teilbar.

Induktionsschritt: Die Aussage sei für alle

${displaystyle m}$

mit

${displaystyle 2leq mleq n}$

erfüllt. Ist nun

${displaystyle n+1}$

eine Primzahl, so ist

${displaystyle n+1}$

selbst der gesuchte Teiler, und die Behauptung ist bewiesen. Ist

${displaystyle ,n+1}$

keine Primzahl, so gibt es zwei Zahlen

${displaystyle a,bin mathbb {N} }$

mit

${displaystyle acdot b=n+1}$

und

${displaystyle 1$

. In diesem Fall besitzt

${displaystyle a}$

gemäß Induktionsannahme (= Induktionsvoraussetzung) einen Primzahl-Teiler, etwa

${displaystyle p}$

. Dann teilt

${displaystyle p}$

auch

${displaystyle n+1}$

und ist Primzahl-Teiler von

${displaystyle n+1}$

. Damit ist auch für diesen zweiten Fall die Behauptung bewiesen.

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Die Aussage

${displaystyle operatorname {A} (n)}$

ist für alle

${displaystyle ngeq n_{0}}$

gültig, wenn Folgendes für jedes beliebige

${displaystyle ngeq n_{0}}$

gezeigt wird:

(Induktionsschritt:)

${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.

Induktionsanfänge, wie sie in der gewöhnlichen Induktion vorkommen, also bspw. der Nachweis der Aussage

${displaystyle operatorname {A} (n_{0})}$

, sind im Induktionsschritt enthalten.^[19] 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.
^[20]

Beweis

Zu zeigen ist: Wenn für alle ${displaystyle ngeq n_{0}}$ aus ${displaystyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}$ ${displaystyle left.{begin{matrix}\\\\end{matrix}}rightrbrace }$ (Induktionsvoraussetzung gewöhnlich ⇒ stark) ${displaystyle operatorname {A} (n)}$ folgt, dann gilt ${displaystyle operatorname {A} (n)}$ für ${displaystyle ngeq n_{0}}$ . (Induktionsschluss gewöhnlich ⇒ stark) Wir definieren die folgende Aussage ${displaystyle operatorname {B} }$ für natürliche Zahlen ${displaystyle nin mathbb {N} ,ngeq n_{0}}$ ${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 ${displaystyle operatorname {B} (n_{0})Longleftrightarrow textstyle bigwedge _{m=n_{0}}^{n_{0}-1}operatorname {A} (m)Longleftrightarrow bigwedge _{min emptyset }operatorname {A} (m)}$ , die leere Und-Verknüpfung ist, gilt ${displaystyle operatorname {B} (n_{0})}$ gemäß Anmerkung[19] sofort. (Gewöhnlicher) Induktionsschritt von ${displaystyle n}$ nach ${displaystyle n+1}$ : Sei ${displaystyle ngeq n_{0}}$ beliebig und es gelte ${displaystyle operatorname {B} (n)}$ , d. h. es gelte ${displaystyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}$ . Wegen der (Induktionsvoraussetzung gewöhnlich ⇒ stark) folgt daraus ${displaystyle operatorname {A} (n)}$ . Zusammengenommen mit ${displaystyle textstyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}$ ergibt dies ${displaystyle bigwedge _{m=n_{0}}^{n}operatorname {A} (m)}$ . Damit haben wir ${displaystyle operatorname {B} (n+1)}$ gezeigt, welches ${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 ${displaystyle nin mathbb {N} ,ngeq n_{0}}$ gilt ${displaystyle operatorname {B} (n)}$ . Wegen ${displaystyle operatorname {B} (n)Longleftrightarrow textstyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}$ ergibt sich a fortiori der starke Induktionsschluss: Für ${displaystyle nin mathbb {N} ,ngeq n_{0}}$ gilt ${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

Induktion mit Vorwärts-Rückwärts-Schritten[Bearbeiten | Quelltext bearbeiten]

Augustin-Louis Cauchy führte 1821 eine Induktionsvariante vor, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (nämlich von

${displaystyle 2^{k}}$

nach

${displaystyle 2^{k+1}}$

) und die entstandenen Lücken nachträglich durch eine rückwärts gerichtete Herleitung von

${displaystyle 2^{k}}$

nach

${displaystyle n<2^{k}}$

auf einen Schlag gefüllt werden.^[21][22]

Beispiel: Ungleichung vom arithmetischen und geometrischen Mittel

Weitere Induktionsvarianten[Bearbeiten | Quelltext bearbeiten]

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

${displaystyle n}$

nach

${displaystyle n+1}$

. Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von

${displaystyle n}$

nach

${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.

Die rekursive Definition – auch induktive Definition genannt^[23][24] – ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird.

Beispiel einer rekursiven Funktion

${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}}}$

${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:

Man kann mit Hilfe der vollständigen Induktion nach

${displaystyle n}$

zeigen, dass

${displaystyle f(x,n)=x^{n}}$

    für

${displaystyle ngeq 0}$

ist.

Der Vorteil dieser rekursiven Definition ist, dass man bei der Berechnung hoher Potenzen nicht

${displaystyle n}$

Multiplikationen, sondern nur Multiplikationen in der Größenordnung von

${displaystyle ln(n)}$

hat.^[25] Sehr hohe Potenzen werden zum Beispiel bei der RSA-Verschlüsselung von Nachrichten verwendet.

Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten.

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. ↑ ^ab 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. ↑ ^ab Maurolycus: Arithemticorum Liber primus, S. 7, Proposition 15^a. 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), digital 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. ↑ ^abc 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 m₀ 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 m₀ 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
    ${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

    ${displaystyle operatorname {A} (m)}$

    für alle Zahlen

    ${displaystyle m}$

    von

    ${displaystyle n_{0}}$

    bis

    ${displaystyle n-1}$

    als gültig angenommen wird.

19. ↑ ^ab Da
    ${displaystyle {mathsf {WAHR}}}$

    das neutrale Element der Und-Verknüpfung ist und deshalb die leere Und-Verknüpfung

    ${displaystyle textstyle bigwedge _{min emptyset }operatorname {A} (m)}$

    den Wahrheitswert

    ${displaystyle {mathsf {WAHR}}}$

    hat, ist die Implikation

    ${displaystyle {bigl (}{mathsf {WAHR}}implies operatorname {A} (n_{0}){bigr )}}$

    durch das Zutreffen von

    ${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
    
    ${displaystyle f(x,40)}$

    
    

    ${displaystyle =f(x^{2},20)}$

    
    

    ${displaystyle =f(x^{4},10)}$

    
    

    ${displaystyle =f(x^{8},5)}$

    
    

    ${displaystyle =x^{8}cdot f(x^{8},4)}$

    
    

    ${displaystyle =x^{8}cdot f(x^{16},2)}$

    
    

    ${displaystyle =x^{8}cdot f(x^{32},1)}$

    
    

    ${displaystyle =x^{8}cdot x^{32}}$

    
    

    ${displaystyle =x^{40}}$

    
    für x=3 wird

    ${displaystyle x^{40}}$

    wird in 6 Rechenschritten berechnet:
    1.

    ${displaystyle x^{2}=3cdot 3=9}$

    
    2.

    ${displaystyle x^{4}=9cdot 9=81}$

    
    3.

    ${displaystyle x^{8}=81cdot 81=}$

    6 561
    4.

    ${displaystyle x^{16}=6561cdot 6561=}$

    43 046 721
    5.

    ${displaystyle x^{32}=43046721cdot 43046721=}$

    1 853 020 188 851 841
    6.

    ${displaystyle x^{40}=6561cdot 1853020188851841=}$

    12 157 665 459 056 928 801