| Das Beweisverfahren der vollständigen Induktion |
| [Anzeige: Die besten Kalender 2010 gibt es hier im Kalender-Shop 2010.] |
II. Das Beweisverfahren der vollständigen Induktion in der Theorie
1. Peanosches Axiomensystem
Giuseppe Peano, ein bedeutender italienischer Mathematiker, der von 1858 bis 1932 lebte, stellte 1889 ein Axiomensystem auf, das mit dem Beweisverfahren der vollständigen Induktion in engem Zusammenhang steht.
Das Peanosche Axiomensystem, charakterisiert die Menge der natürlichen Zahlen auf Basis der Nachfolger:
" I) 1 ist eine natürliche Zahl
II) Jede natürliche Zahl hat genau einen Nachfolger
III) Der Nachfolger ist nie gleich 1
IV) Verschiedene Zahlen haben nie denselben Nachfolger
V) Ist L eine Teilmenge der natürlichen Zahlen mit den beiden Eigenschaften
1) 1 in L
2) k in L => (k+1) in L so ist L = N" [N die Menge aller natürlichen Zahlen] (zitiert aus: Anschauliche Analysis 1, S. 204)
Dieses letzte Axiom wird auch "Axiom der vollständigen Induktion" genannt, da die vollständige Induktion darauf basiert.
|
2. Blaise Pascal
Blaise Pascal, der Erfinder des Beweisverfahrens der vollständigen Induktion, lebte von 1623 bis 1662 in Frankreich. Er war einer der bedeutendsten Mathematiker und Physiker seiner Zeit. Im mathematischen Bereich seiner Tätigkeit wurde er vor allem durch eine Abhandlung über Kegelschnitte, den Bau von Rechenmaschinen, das Erweitern der Kombinationslehre und der Wahrscheinlichkeitsrechnung und durch Arbeiten über Rollkurven (Zykloide) berühmt. Das "Pascalsche Koeffizienten-Schema" (auch als Pascalsches Dreieck bekannt), mit dem man binomische Formeln höheren Grades aufstellen kann, stammt auch von ihm. In der Physik ist sein Name noch heute in der Druckeinheit Pascal verewigt, da er den Luftdruck entdeckt hat. Pascal gilt außerdem als größtes religiöses Genie des modernen Frankreichs, da er neben seinen mathematischen Tätigkeiten noch in einer Schrift das Christentum verteidigte.
Schließlich erfand er auch das Beweisverfahren der vollständigen Induktion. Dieses Verfahren veröffentlichte Blaise Pascal in der "Conséquence douzième" des "Traité du Triangle Arithmétique", das 1654 gedruckt aber erst 1665 veröffentlicht wurde.
|
3. Das Beweisverfahren der vollständigen Induktion
3.1. Erläuterung des Verfahrens
Das Beweisverfahren der vollständigen Induktion basiert auf den oben genannten Peanoschen Axiomen. Vor allem das letzte Axiom ist dafür von großer Bedeutung.
Das Prinzip der vollständigen Induktion ist folgendes: Wenn eine Aussage für n = 1 gilt und wenn man unter Annahme der Richtigkeit der Aussage für n = k die Richtigkeit für n = k + 1 beweisen kann, gilt die Aussage für alle n in N.
Aus der Formulierung des Prinzips der vollständigen Induktion folgt, daß das Beweisverfahren der vollständigen Induktion aus mehreren Schritten besteht:
Zuerst beweist man, daß die Aussage für n = 1 gilt. Als Zweites nimmt man an, daß die Aussage für n = k gilt, und überprüft schließlich, ob sie dann auch für n = k + 1 gilt. Wenn diese Bedingungen erfüllt sind, gilt die Aussage für alle natürlichen Zahlen.
In mathematischen Formeln ausgedrückt sehen die drei Schritte dann so aus:
I) Beweis: Aussage gilt für n = 1
II) Annahme: Aussage gilt für n = k
III) Beweis: Aussage gilt für n = k + 1, wenn sie für n = k gilt.
=> Aussage gilt für n in N
|
3.2. einfaches Beispiel
Ein einfaches Beispiel zum besseren Verständnis:
Zu beweisen sei:
Alle Vielfachen von 10 haben die Endziffer 0 (bei Multiplikation mit natürlichen Zahlen).
In Formeln: n * 10 = ?0 ("?" steht hier für beliebige Ziffernfolgen)
I) Beweis für n = 1:
1 * 10 = 10 => Aussage wahr für n = 1
II) Annahme für n = k:
k * 10 = ?0
III) Beweis für n = k +1 unter Annahme aus II:
(k + 1) * 10 = k * 10 + 1 * 10 = ?0 + 10 = ?0
(da die letzten Ziffern zuerst addiert werden.)
=> Aussage wahr für n = k + 1, wenn sie für n = k gilt
=> Jedes Vielfache von 10 hat die Endziffer 0.
Natürlich gibt es bei diesem Beispiel auch einfachere Lösungswege.
|
3.3. Beweis der Richtigkeit des Beweisverfahrens
An diesem Beispiel sieht man, daß das Beweisverfahren der vollständigen Induktion hier funktioniert, also könnte man annehmen, daß es immer gilt.
Da Annahmen in der Mathematik jedoch nicht als Beweis gelten, muß man nun erst mal beweisen, daß das Verfahren überhaupt als Beweis zulässig ist. Dazu gibt es zwei Möglichkeiten. Zum einen den Beweis durch Logik zum anderen durch den Versuch eines Gegenbeweises.
|
3.3.1. Beweis durch Logik
Wenn man sich die einzelnen Schritte des Beweises noch einmal ansieht und überlegt, was sie eigentlich bedeuten, erkennt man ziemlich schnell die Richtigkeit des Beweisverfahrens.
Hier also noch einmal die Schritte des Beweisverfahrens der vollständigen Induktion:
I) Beweis: Aussage gilt für n = 1
II) Annahme: Aussage gilt für n = k
III) Beweis: Aussage gilt für n = k + 1, wenn sie für n = k gilt.
=> Aussage gilt für alle n in N
Zuerst beweist man also, daß die Aussage für 1 gilt.
Anschließend beweist man, daß die Aussage, wenn sie für ein beliebiges k gilt, auch für k + 1 gilt.
Da k beliebig ist kann k auch 1 sein. Für n = 1 gilt die Aussage wie in Schritt I bewiesen, also setzt man k = 1, um den nächsten Wert (k + 1) zu berechnen, für den die Aussage gilt. Die Aussage gilt für k = 1, also muß sie auch für k + 1 = 2 gelten, da in Schritt III bewiesen wurde, daß die Aussage, wenn sie für ein beliebiges k gilt, auch für k + 1 gilt.
Nun hat man also über Schritt III bewiesen, daß die Aussage nicht nur für n = 1 sondern auch für n = 2 gilt. Daraus folgt auf demselben Weg - man setzt k = 2 - daß die Aussage auch für n = 3 gilt. Dadurch läßt sich wiederum beweisen, daß die Aussage für n = 4 gilt und so weiter.
Die Aussage gilt dann also für alle ganzen Zahlen von 1 bis unendlich, also für alle n in N.
Damit ist also bewiesen, daß das Beweisverfahren der vollständigen Induktion ein zulässiges Beweisverfahren für Aussagen über die natürlichen Zahlen ist.
Da dies jedoch nicht wirklich ein mathematischer Beweis ist, hier noch der Beweis durch den Versuch eines Gegenbeweises:
|
3.3.2. Beweis durch Versuch eines Gegenbeweises
Der Beweis des Verfahrens über den Versuch des Gegenbeweises funktioniert ähnlich. Es gebe eine Zahl m > 1 für die trotz der Schritte der vollständigen Induktion die Aussage falsch ist. Diese Zahl soll die kleinste Zahl sein, für die die Aussage falsch ist.
Die Aussage gilt also für n = 1 und für alle nachfolgenden Zahlen bis m - 1. Aus Schritt III der vollständigen Induktion folgt aber: Die Aussage gilt auch für n = (m-1)+1 = m. Dies ist ein Widerspruch, da nach Annahme die Aussage für n = m nicht gelten darf. Es gibt also keine Zahl m>1, für die die Aussage nicht gilt. Also gilt sie für alle Zahlen.
Der Gegenbeweis ist also nicht möglich, also ist auch dadurch bewiesen, daß das Beweisverfahren der vollständigen Induktion funktioniert.
|
4. Das Beweisverfahren für Zahlen größer n0
4.1. Erläuterung des Verfahrens
Das Beweisverfahren der vollständigen Induktion läßt sich aber auch einschränken.
Man kann damit also nicht nur beweisen, daß eine Aussage auf dem Intervall [1; oo[ sondern auch auf [n0; oo[ mit n0 in N gilt, wobei das Intervall selbstverständlich nur natürliche Zahlen enthalten darf.
Die Schritte des Beweisverfahrens ändern sich dann natürlich auch:
I) Beweis: Aussage gilt für n = n0
II) Annahme: Aussage gilt für n = k (k >= n0)
III) Beweis: Aussage gilt für n = k + 1, wenn sie für n = k gilt.
=> Aussage gilt für alle n >= n0; n in N
|
4.2. einfaches Beispiel
Auch hier wieder ein einfaches Beispiel zum Verständnis:
Behauptung:
Jedes Vielfache von fünf, dessen Faktor größer oder gleich 6 ist, ist größer 27.
n0 ist also hier 6, die Schritte des Beweises lauten also:
I) Beweis: Aussage gilt für n = 6:
6 * 5 = 30 > 27 q.e.d.
II) Annahme: Aussage gilt für n = k:
=> k * 5 > 27
III) Beweis: Aussage gilt für n = k + 1, wenn sie für n = k gilt:
(k + 1) * 5 = k * 5 + 1 * 5 = k * 5 + 5 > 27, da k * 5 schon größer 27 ist. q.e.d.
=> Jedes Vielfache von fünf, dessen Faktor größer oder gleich 6 ist, ist größer 27.
Dieses Beispiel hätte man natürlich auch auf einem deutlich einfacheren Weg lösen können.
Diese Abwandlung des Verfahrens läßt sich auf demselben Weg beweisen wie das Beweisverfahren selbst.
|
5. Abwandlung des Beweisverfahrens für negative Zahlen
5.1. Erläuterung
Wenn man sich länger mit dem Thema vollständige Induktion beschäftigt, stellt man fest, daß man es durch eine geringe Abwandlung auch für negative Zahlen verwenden kann.
Ich möchte allerdings betonen, daß das folgende Verfahren nur eine selbst erdachte Abwandlung ist und selbst nicht als vollständige Induktion bezeichnet werden kann, da sich diese immer auf natürliche Zahlen bezieht.
Man beginnt den Beweis einer Aussage dann bei -1 statt bei 1 und beweist, daß die Aussage, wenn sie für n = k gilt, auch für n = k - 1 gilt.
Die Schritte des Beweisverfahrens lauten dann, in mathematischen Formeln ausgedrückt:
I) Beweis: Aussage gilt für n = -1
II) Annahme: Aussage gilt für n = k
III) Beweis: Aussage gilt für n = k - 1, wenn sie für n = k gilt.
=> Aussage gilt für n in Z-
|
5.2. einfaches Beispiel
Auch hierzu wieder ein einfaches Beispiel:
Das Produkt einer beliebigen negativen Zahl mit 2 gibt eine gerade, negative Zahl.
Beweis:
I) Beweis: Aussage gilt für n = -1: (-1) * 2 = -2 (= negativ, gerade) q.e.d.
II) Annahme: Aussage gilt für n = k; k in Z-: k * (2) = negativ, gerade
III) Beweis: Aussage gilt für n = k - 1, wenn sie für n = k gilt:
(k - 1) * (2) = k * (2) + (-1) * (2) = (negativ, gerade) - 2 = negativ, gerade
=> Aussage gilt für alle n in Z-
Man muß bei dieser Abwandlung des Beweisverfahrens aber immer darauf achten, daß es sich um negative Zahlen handelt, da diese bei gewissen Rechnungen (z.B. Logarithmus) besonders beachtet werden müssen.
Natürlich läßt sich auch das Beweisverfahren für negative Zahlen einschränken, indem man die größte Zahl, für die die Aussage gilt, als n0 bezeichnet und an die Stelle von -1 setzt.
|
5.3. Beweis der Abwandlung für negative Zahlen
Der Beweis dieser Abwandlung der vollständigen Induktion für negative Zahlen funktioniert ähnlich wie der für positive Zahlen.
Man sucht sich die größte Zahl, für die die Aussage gilt, also -1. Da die Aussage für n = -1 gilt, folgt, daß sie auch für n = -2 gilt, da ja bewiesen wurde, daß aus der Richtigkeit der Aussage für n = k, die Richtigkeit für n = k - 1 folgt. Dies läßt sich dann im Negativen bis ins Unendliche fortführen, woraus folgt, daß die Aussage dann von -1 bis -oo, also für Z- gilt.
Damit ist also das Verfahren auch für negative Zahlen bewiesen.
Der Beweis wäre natürlich auch hier wieder über den Versuch eines Gegenbeweises möglich.
|
6. Beweis von Aussagen für alle ganzen Zahlen
Wenn man nun eine Aussage für alle ganzen Zahlen beweisen will, tut man dies in drei Schritten:
1. Beweis der Aussage für alle natürlichen Zahlen ([ 1; oo[) mit dem Beweisverfahren der vollständigen Induktion
2. Beweis der Aussage für alle negativen ganzen Zahlen (] -oo; -1]) mit der Abwandlung des Beweisverfahrens der vollständigen Induktion für negative Zahlen
3. Beweis der Aussage für n = 0 durch Rechnung
In einem Schritt wäre dies mit dem Beweisverfahren der vollständigen Induktion unmöglich, da man sonst als erstes beweisen müßte, daß die Aussage für +oo oder -oo gilt, was nicht möglich ist.
|
Datum: Januar 2000
Fach: Mathematik
Jahrgangsstufe: K12 / K13 (Gymnasium)
Schule: Heinrich-Heine-Gymnasium, München
Punkte: 14 (Note: 1)
|
© Copyright 1998-2009 by Klaus Fangmann, www.retira.de
Alle Rechte vorbehalten! |
