Vollständige Induktion

Vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann solch ein Beweis nicht für alle Einzelfälle durchgeführt werden. Er wird daher in zwei Etappen durchgeführt: als Induktionsanfang für eine kleinste Zahl (meist 1 oder 0) und als Induktionsschritt, der aus der Aussage für eine variable Zahl die entsprechende Aussage für die nächste Zahl logisch ableitet. Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik.

Veranschaulichung

konkrete Induktionsschritte

Die vollständige Induktion erfasst durch den variablen Induktionsschritt beliebig viele Schritte, die man von 1 aus konkret durchführen kann. Das verdeutlicht die Graphik links. Diese Methode 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 irgendwann umfallen. Im Unterschied zum Domino, bei dem zwar beliebig viele, aber immer endlich viele Steine vorliegen, gibt es aber unendlich viele natürliche Zahlen, so dass keine beliebig lange konkrete Induktion alle Zahlen erreicht. Nur über den variablen Induktionsschritt wird die Induktion vollständig und erreicht tatsächlich alle Zahlen.

vollständige Induktion als Dominoeffekt

Etymologie und Geschichte

Die Bezeichnung „Vollständige Induktion“ leitet sich ab von lat. inductio (= ‚Herein-‘ oder ‚Hinaufführung‘). Der Beiname „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. Das Interesse an induktiven Beweisen erwachte erst allmählich in der Neuzeit. Der erste bekannte explizite Beweis per vollständiger Induktion (unten ausgeführt) findet sich 1575 in dem Werk Arithmeticorum Libri Duo von Franciscus Maurolicus, ohne dass dort aber das Beweisverfahren erörtert wird. Das allgemeine Induktionsprizip mit Induktionsanfang und Induktionsschritt thematisierte erst Blaise Pascal in seinem Traite au Trinagle Arithmetique von 1654. Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob 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 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 ein Satz für alle natürlichen Zahlen n gilt, genügt es zu zeigen, dass er für n=1 gilt und dass aus der Gültigkeit des Satzes für eine Zahl n stets seine Gültigkeit auch für die folgende Zahl n+1 folgt.

Als formale Schlussregel mit dem Ableitungsoperator lautet die vollständige Induktion für eine Aussage $\,A(x)$:

$\,A(1){,}\quad n\in \mathbb {N} \land A(n)\Rightarrow A(n+1)\ \vdash \forall n\in \mathbb {N} \colon A(n)$

Als Induktionsanfang gilt hierbei der Beweis von $\,A(1)$ und als Induktionsschritt der Beweis von $\,A(n+1)$ mit der Induktionsvoraussetzung $n\in \mathbb {N} \land A(n)$. Der Induktionsanfang lautet $\,A(0)$, falls man die Null zu den natürlichen Zahlen zählt, was manchmal vereinbart wird. Zur Beweisvereinfachung wird der Induktionsschritt oft nicht von $\,n$ auf $\,n+1$ durchgeführt, sondern von $\,n-1$ auf $\,n$; dies ist lediglich eine Notationsänderung.

Herleitung

Die vollständige Induktion kann aus Axiomen für die natürlichen Zahlen hergeleitet werden. Am bekanntesten ist die Ableitung aus dem fünften Peano-Axiom, dem sogenannten Induktionsaxiom, das mit 1 als kleinster Zahl folgendermaßen lautet: Ist $\,1$ ein Element von $\,K$ und ist mit $\,n$ aus $\,K$ stets auch $\,n+1$ aus $\,K$, dann ist $\mathbb {N}$ eine Teilmenge von $\,K$. Hieraus ergibt sich die vollständige Induktion für $\,K$ als Menge aller natürlicher Zahlen $\,n$, die die Aussage $\,A(n)$ erfüllen.

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
• als kleinste induktive Menge, das heißt, als kleinste Menge, die das Unendlichkeitsaxiom von Zermelo erfüllt
• als Menge der endlichen Ordinalzahlen

Beispiele

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

Summe ungerader Zahlen (Maurolicus 1575)

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

1 = 1

1 + 3 = 4

1 + 3 + 5 = 9

1 + 3 + 5 + 7 = 16

Der allgemeine Satz lautet: $\sum _{i=1}^{n}(2i-1)=n^{2}.$. Für diesen Satz formulierte Maurolicus 1575 den ältesten Beweis mit vollständiger Induktion. Ein Beweis mit heute geläufigen Rechenregeln liest sich folgendermaßen:

Der Induktionsanfang gilt wegen $\sum _{i=1}^{1}(2i-1)=2\cdot 1-1=1=1^{2}$.

Beim Induktionsschritt ist zu zeigen: Wenn $\sum _{i=1}^{n}(2i-1)=n^{2}$, dann $\sum _{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: $\sum _{i=1}^{n+1}(2i-1)=\sum _{i=1}^{n}(2i-1)+(2(n+1)-1)=n^{2}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}$.

Gaußsche Summenformel

Die Gaußsche Summenformel lautet: Für alle natürliche Zahlen $\,n$ gilt

$\sum _{k=1}^{n}k=1+2+\cdots +n={\frac {n(n+1)}{2}}$

Der Induktionsanfang ergibt sich unmittelbar:

$\sum _{k=1}^{1}k=1={\frac {1(1+1)}{2}}$

Der Induktionsschritt für beliebige natürliche Zahlen $\,n$ wird über folgende Gleichungskette gewonnen, bei der die Induktionsvoraussetzung bei der zweiten Umformung angewandt wird:

${\begin{aligned}\sum _{k=1}^{n+1}k=\sum _{k=1}^{n}k+(n+1)={\frac {n(n+1)}{2}}+(n+1)=\\={\frac {n(n+1)+2(n+1)}{2}}={\frac {(n+1)((n+1)+1)}{2}}\end{aligned}}$

Bernoullische Ungleichung

Die Bernoullische Ungleichung lautet: Für reelle Zahlen $\,x$ mit $x+1\geq 0$ und natürliche Zahlen $n\geq 0$ gilt

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

Der Induktionsanfang gilt hier wegen $(1+x)^{0}=1\geq 1$. Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung anwendet:

${\begin{aligned}(1+x)^{n+1}=(1+x)^{n}\cdot (1+x)\geq (1+nx)\cdot (1+x)=\\=1+x+nx+nx^{2}\geq 1+x+nx=1+(n+1)x\end{aligned}}$

Varianten

Induktion mit beliebigem Anfang

Der Induktionsbeweis ist auch für Aussagen möglich, die nicht für alle natürlichen Zahlen, sondern nur für alle Zahlen ab einem gewissen Anfangswert gelten. Dies ist die allgemeinere Beweistechnik von Dedekind. Beispielsweise lässt sich die Ungleichung $2^{n}\geq n^{2}$ für natürliche Zahlen $n\geq 4$ zeigen:

Der Induktionsanfang für $\,n=4$ ergibt sich mit $2^{4}=16\geq 16=4^{2}$.

Der Induktionsschritt $n\geq 4$ gilt aufgrund folgender Ableitung, die im zweiten Schritt die Induktionsvoraussetzung anwendet:

$2^{n+1}=2\cdot 2^{n}\geq 2n^{2}=n^{2}+n^{2}\geq n^{2}+4n\geq n^{2}+2n+1=(n+1)^{2}$.

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=1$ und $\,n=3$ offenbar falsch.

Induktion für ganze Zahlen (positiv und negativ)

Der Induktionsbeweis ist auch für Aussagen möglich, die nicht nur für alle natürlichen Zahlen, sondern auch für alle negativen Zahlen gelten. Dafür beginnt man mit einem beliebigen Startwert und beweist den positiven Induktionsschritt von n nach n+1 und anschließend den Induktionsschritt in negativer Richtung von n nach n−1. Beim Induktionsanfang 0 kann man den zweiten Induktionsschritt auch von n nach −n zeigen.

Induktion mit mehreren Vorgängern

Manchmal ist es notwendig, im Induktionsschritt die Gültigkeit für mehrere Vorgänger vorauszusetzen. Der Induktionsanfang ist dann für mehrere Startwerte durchzuführen. Mit Startwerten $\,n=0$ und $\,n=1$ kann man die Formeln für $\,n$ und $\,n-1$ als Induktionsvoraussetzung nehmen (vergleiche den Beweis der Formel von Binet für die Fibonacci-Folge). Als Induktionsvoraussetzung kann auch die Gültigkeit der Aussage für alle Zahlen $\,m$, die größer oder gleich dem Startwert und kleiner oder gleich $\,n$ sind, angenommen werden. Diese Induktion zweiter Art lässt sich aus der vollständigen Induktion ableiten.

Ein einfaches Beispiel ist der Beweis, dass jede natürliche Zahl $n\geq 2$ einen Primzahl-Teiler hat. Induktionsanfang: 2 ist durch die Primzahl 2 teilbar. Induktionsschritt: Die Aussage sei für alle $\,m$ mit $2\leq m\leq n$ erfüllt. Ist nun $\,n+1$ eine Primzahl, so ist $\,n+1$ selbst der gesuchte Teiler. Ist $\,n+1$ keine Primzahl, so gibt es zwei Zahlen $\,a,b$ mit $a\cdot b=n+1$ und $2\leq a,b\leq n$. Beide Zahlen erfüllen also die Induktionsvoraussetzung. Insbesondere besitzt $\,a$ einen Primzahl-Teiler $\,p$. $\,p$ teilt auch $\,n+1$ und ist somit ein Primzahl-Teiler von $\,n+1$.

Ein anderes Beispiel, bei dem die Gültigkeit der Induktionsvoraussetzung für alle Vorgänger verwendet wird, ist der Beweis des Zeckendorf-Theorems.

Vorwärts-Rückwärts-Induktion

Cauchy führte 1821 eine Induktionsvariante ein, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (etwa von n nach 2n) und die entstehenden Lücken anschließend durch einen rückwärts gerichteten Induktionsschritt von n nach n−1 gefüllt werden.

Transfinite und strukturelle Induktion

Die vollständige Induktion ist von natürlichen Zahlen verallgemeinerbar auf Ordinalzahlen; bei Ordinalzahlen, die mächtiger 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 Ordnungstruktur aufweisen; hier spricht man zuweilen von struktureller Induktion.

rekursive oder induktive Definition

Die rekursive Definition - früher auch induktive Definition genannt - ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird. Ein konstruktiver Beweis mit vollständiger Induktion kann eine rekursive Berechnung ersparen. Zum Beispiel erspart die Gaußsche Summenformel eine rekursive Berechnung der Summe $\sum _{k=1}^{n}k$ über den Rekursionsanfang $\sum _{k=1}^{1}k=1$ und den Rekursionsschritt $\sum _{k=1}^{n+1}k=\sum _{k=1}^{n}k+n+1$.

Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten.

Weblinks

• http://henked.de/begriffe/induktion.htm Vollständige Induktion
• http://www.emath.de/Referate/Induktion-Aufgaben-Loesungen.pdf Umfangreiche Aufgabensammlung zur vollständigen Induktion mit Lösungen
• Vollständige Induktion einfach erklärt auf YouTube