Hauptmenü öffnen

Vollständige Induktion

Mathematische Beweismethode

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 alle Einzelfälle erbracht werden.

Der Beweis, dass die Aussage für alle ( meist 1 oder 0) gilt, wird daher in zwei Etappen durchgeführt:

  1. Im Induktionsanfang wird die Aussage für eine kleinste Zahl hergeleitet.
  2. Im Induktionsschritt wird die Aussage aus der Aussage für hergeleitet.

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

Inhaltsverzeichnis

AussageformenBearbeiten

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

Beispiel (Siehe Gaußsche Summenformel):

  für  

Wenn man Werte für   einsetzt, erhält man Aussagen, die wahr oder falsch sind.

  
 
 
 

In dem Beispiel sind sie offensichtlich alle wahr. Da man dies nicht für alle (unendlich viele) Zahlen nachrechnen kann, bedarf es eines besonderen Beweisverfahrens. Dies liefert die vollständige Induktion.

Die Aussageform   ist allgemeingültig, wenn sie für alle   wahr ist.

Um die Allgemeingültigkeit der Aussageform   zu beweisen, zeigt man Folgendes:

  1.   (Induktionsanfang) und
  2. aus der Aussage (der Induktionsannahme)   folgt die Aussage  . (Das ist der Induktionsschritt.)[1]

VeranschaulichungBearbeiten

 
Vollständige Induktion als Dominoeffekt mit unendlich vielen Steinen

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

Die Allgemeingültigkeit einer Aussageform   ist für n = 1, 2, 3, … bewiesen, wenn   gültig ist (der erste Stein fällt um) und wenn zusätzlich gilt   für n = 1, 2, 3, … (jeder Stein reißt beim Umfallen den nächsten Stein mit).

Etymologie und GeschichteBearbeiten

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.

DefinitionBearbeiten

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

Um zu beweisen, dass ein Satz für alle natürlichen Zahlen   gilt, genügt es zu zeigen, dass er für   gilt und dass aus der Gültigkeit des Satzes für eine Zahl   stets seine Gültigkeit auch für die folgende Zahl   folgt.[9]

Als formale Schlussregel mit Ableitungsoperator   lautet die vollständige Induktion für eine Aussage   und eine natürliche Zahl  :

 

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

Soll die Formel   für alle natürlichen Zahlen   bewiesen werden, dann genügen dazu zwei Beweisschritte:
  1. der Induktionsanfang: der Beweis von  ,
  2. der Induktionsschritt: der Beweis der Induktionsbehauptung   aus   und der Induktionsvoraussetzung (auch Induktionsannahme)  .
Nach obiger Schlussregel folgt dann die Verallgemeinerung der Formel   auf alle natürlichen Zahlen   (der abschließende Induktionsschluss).

Meist ist   oder  .   ist jedoch möglich.


Da die Aussage   für   gleichwertig ist zur Aussage   für  , lässt sich Dedekinds Induktion auf die vollständige Induktion von 0 aus zurückführen:[11]

 

Die Axiomatik der natürlichen Zahlen durch PeanoBearbeiten

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

Das Axiom der vollständigen InduktionBearbeiten

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   eine Teilmenge der natürlichen Zahlen   mit den Eigenschaften:

  1.   ist ein Element von  
  2. Mit   aus   ist stets auch   aus  ,

dann ist  .

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[14]
  • als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht[15][16]
  • 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

BeispieleBearbeiten

Gaußsche SummenformelBearbeiten

Die Gaußsche Summenformel lautet: Für alle natürlichen Zahlen   gilt

       

Sie kann durch vollständige Induktion bewiesen werden.

Der Induktionsanfang ergibt sich unmittelbar:

       .

Im Induktionsschritt ist zu zeigen, dass aus der Induktionsvoraussetzung

       

die Induktionsbehauptung

        für  

folgt. Dies gelingt folgendermaßen:

    (Hauptnenner 2)
  (Ausklammern von  )

Schließlich der Induktionsschluss: Damit ist die Aussage A(n) für alle n ≥ 1 bewiesen.

Summe ungerader Zahlen (Maurolicus 1575)Bearbeiten

Beweis der Summenformel über ungerade Zahlen mit Hilfe der vollständigen Induktion

Die schrittweise Berechnung der Summe der ersten   ungeraden Zahlen legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von   bis   ist gleich dem Quadrat von  :

1 = 1
1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16

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

Der Induktionsanfang gilt wegen  .

Beim Induktionsschritt ist zu zeigen: Wenn  , dann  . Er ergibt sich über folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:

 .

Bernoullische UngleichungBearbeiten

Die Bernoullische Ungleichung lautet für reelle Zahlen   mit   und natürliche Zahlen  

 .

Der Induktionsanfang gilt hier wegen   (wenn man der Konvention   folgt). Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei obige Bedingung für   dafür sorgt, dass der Term nicht negativ wird:

 

InduktionsvariantenBearbeiten

Induktion mit beliebigem AnfangBearbeiten

Induktionsbeweis der Ungleichung   für natürliche Zahlen  :

Der Induktionsanfang für   ergibt sich mit  .
Der Induktionsschritt gilt aufgrund folgender Ableitung, die im zweiten Schritt die Induktionsvoraussetzung und im vierten und sechsten Schritt die Voraussetzung   anwendet:
 .

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

Induktion mit mehreren VorgängernBearbeiten

In manchen Induktionsbeweisen benötigt man eine Induktionsvoraussetzung für mehrere Vorgänger; der Induktionsanfang ist dann für mehrere Startwerte durchzuführen. Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung für n und n−1 nötig, dann ist ein Induktionsanfang für zwei aufeinander folgende Zahlen, also etwa 0 und 1, erforderlich.[17] Als Induktionsvoraussetzung kann auch die Aussage für alle Zahlen zwischen dem Startwert und n dienen. Ein Beispiel[18] ist der Beweis, dass jede natürliche Zahl   einen Primzahl-Teiler hat:

Induktionsanfang: 2 ist durch die Primzahl 2 teilbar. Induktionsschritt: Die Aussage sei für alle   mit   erfüllt. Ist nun   eine Primzahl, so ist   selbst der gesuchte Teiler. Ist   keine Primzahl, so gibt es zwei Zahlen   mit   und  . Beide Zahlen erfüllen also die Induktionsvoraussetzung. Insbesondere besitzt   einen Primzahl-Teiler  .   teilt auch   und ist somit ein Primzahl-Teiler von  .

Starke InduktionBearbeiten

Die Aussage   ist für alle   gültig, wenn Folgendes für ein beliebiges   gezeigt wird:

(Induktionsschritt:) Die Aussage   (die Induktionsbehauptung) folgt aus
      (Induktionsvoraussetzung)[19]
(Induktionsschluss:) Damit gilt die Aussage   für alle  .

Der Induktionsanfang, d. i. die Aussage  , ist im Induktionsschritt mit der für   leeren Induktionsvoraussetzung nachzuweisen.[20] Es kann überdies vorkommen, dass mehr als eine Anfangsaussage vorab zu zeigen istd (siehe Fibonacci-Folge).

Beispiel: Fibonacci-Folge#Induktiver Beweis

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

Beweis  

Zu zeigen ist:

Wenn für alle  
aus     (Induktionsvoraussetzung gewöhnlich ⇒ stark)
  folgt,
dann gilt
  für alle  . (Induktionsschluss gewöhnlich ⇒ stark)

Wir definieren die folgende Aussage   für natürliche Zahlen  

 

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

Induktionsanfang: Hier ist nichts zu zeigen, da  , d. h.  , die leere Aussage ist.

Induktionsschritt von   nach  :

Sei   beliebig und es gelte  , d. h. es gelte
 .
Wegen der (Induktionsvoraussetzung gewöhnlich ⇒ stark) folgt daraus
 .
Zusammengenommen mit   ergibt dies
 .

Damit haben wir   gezeigt, und der gewöhnliche Induktionsschritt ist fertig. Wir schließen (gewöhnlicher Induktionsschluss):

Für alle   gilt  .

Wegen   ergibt sich a fortiori der starke Induktionsschluss:

Für alle   gilt  .

Trotz dieser 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.

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

Augustin-Louis Cauchy führte 1821 eine Induktionsvariante vor, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (etwa von   nach  ) und die entstehenden Lücken nachträglich durch einen rückwärts gerichteten Induktionsschritt von   nach   gefüllt werden.[22][23]

1
 ↓
 2
 ↓
 4→ 3
 ↓
 8→ 7→ 6→ 5
 ↓
16→ 15→ 14→ 13→ 12→ 11→ 10→ 9
 ↓
32→ 31→ 30→ 29→ 28→ 27→ 26→ 25→ 24→ 23→ 22→ 21→ 20→ 19→ 18→ 17
 ↓ ...

Beispiel: Ungleichung vom arithmetischen und geometrischen Mittel

Weitere InduktionsvariantenBearbeiten

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   nach  . Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von   nach   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 DefinitionBearbeiten

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

Beispiel einer rekursiven Funktion

 

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

  

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 Funktion nach   zeigen, dass

  für n≥0 ist.

Der Vorteil dieser rekursiven Funktion ist, dass man bei der Berechnung hoher Potenzen nicht   Multiplikationen, sondern nur Multiplikationen in der Größenordnung von   hat.[26] Sehr hohe Potenzen werden zum Beispiel bei der RSA-Verschlüsselung von Nachrichten verwendet.

Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten.

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  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. a b 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. a b 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), 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. a b 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. Man kann die Aussage   durch   definieren und mit ihr die Induktion mit Induktionsanfang   durchführen.
  12. Peano: Arithmetices principia nova methodo exposita. 1889. In: G. Peano: Opere scelte. Band II. Rom 1958. S. 35–36, 40–41.
  13. ausführliche Beweise auch in: Edmund Landau: Grundlagen der Analysis. Leipzig 1930.
  14. Felscher: Naive Mengen und abstrakte Zahlen I, S. 130–132.
  15. Dedekind: Was sind und was sollen die Zahlen?, § 6, Erklärung 71.
  16. dargestellt als Dedekind-Tripel in: Felscher: Naive Mengen und abstrakte Zahlen I, S. 147.
  17. vergleiche den Beweis der Formel von Binet für die Fibonacci-Folge
  18. Ein Beispiel ist auch der Beweis des Zeckendorf-Theorems; Der Satz von Zeckendorf
  19. Definitionsgemäß ist  .
    Man kann beim Beweis der Induktionsbehauptung also voraussetzen, dass   für alle Zahlen   von   bis   gilt.
  20. Da   das neutrale Element der Und-Verknüpfung ist und deshalb die leere Und-Verknüpfung   den Wahrheitswert   ergibt, ist die Implikation   durch das Zutreffen von   nachzuweisen.
  21. Oliver Deiser Einführung in die Mathematik.
    Der hauptsächliche Unterschied des starken Induktionsschemas zum gewöhnlichen ist – wie der Beweis zeigt, dass die vom gewöhnlichen Schema verwendeten (und quasi weggeworfenen) Induktionsvoraussetzungen beim starken Schema erhalten bleiben.
  22. Cauchy, Augustin-Louis. Analyse algebrique. Paris 1821. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel ist dort auf Seite 457 ff.
  23. 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.
  24. Hausdorff: Grundzüge der Mengenlehre. 1914. S. 112–113 eingeschränkte Vorschau in der Google-Buchsuche.
  25. Peano: Le Definitione in Matematica. In: Opere scelte. Band II, 1921. S. 431, § 7 Definizioni per induzione.
  26. Zum Beispiel errechnet sich                  
    für x=3 wird   wird in 6 Rechenschritten berechnet:
    1.  
    2.  
    3.  6 561
    4.  43 046 721
    5.  1 853 020 188 851 841
    6.  12 157 665 459 056 928 801
  Dieser Artikel wurde am 15. Juli 2010 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.