Das Beweisverfahren der vollständigen Induktion und seine Anwendung

Inhalt

Einleitung

- Begriffsklärung: Was versteht man unter Induktion?

- Herleitung des Verfahrens der vollständigen Induktion an Hand eines Beispiels

- Das Prinzip der vollständigen Induktion
- Vorgehensweise bei der praktischen Anwendung
- Schematische Darstellung des Beweisprinzips der vollständigen Induktion

- Der strenge Beweischarakter der vollständigen Induktion
- demonstriert an Hand von Gegenbeispielen

-¨ Beweis der BERNOULLIschen Ungleichung mit Hilfe vollständiger Induktion

Schlußwort

- Quellennachweis

Einleitung

Die daliegende Facharbeit befaßt sich mit dem Beweisverfahren der vollständigen Induktion und deren Anwendungsgebieten. Hierbei wird auf die Herleitung des Beweisprinzips eingegangen, sowie auf seinen strengen Beweischarakter. Der praktische Gebrauch dieser Methode wird anschließend ausführlich an einem Beispiel, dem Beweis der BERNOULLIschen Ungleichung, demonstriert und das Auftreten eines Widerspruchs an Hand von Gegenbeispielen gesondert behandelt.

In folgendem Verlauf der Facharbeit soll mit "A" eine mathematische Aussage, sprich eine Zahlenfolge oder ein mathematischer Satz, bezeichnet werden. Die getroffenen Schlüsse über "A" beziehen sich immer auf eine beliebige Zahl n, wobei n Element der Menge der natürlichen Zahlen, ausgenommen der 0, ist (n[Abbildung in dieser Leseprobe nicht enthalten]N).

Das Peanosche Axiomensystem der natürlichen Zahlen wird hierbei als bekannt vorausgesetzt und bei den Berechnungen wird nicht direkt darauf eingegangen.

Ferner gelten die Axiome der elementaren Rechenoperationen.

Begriffsklärung: Was versteht man unter Induktion?

Bei der Definition der Induktion muß man zwischen 1. der empirischen Induktion in den Naturwissenschaften und 2. der vollständigen Induktion in der Mathematik unterscheiden.

1. Die Erkenntnisse vieler Naturgesetze, wie z.B. die Mendelschen Vererbungsgesetze in der Biologie, das Ohmsche Gesetz der Elektrizitätslehre, das Gesetz der multiplen Proportionen in der Chemie, u.v.a. basiert auf empirischer Induktion.

Genauer formuliert: Durch experimentelle Beobachtung von Einzelfällen wird auf die allgemeine Gültigkeit der auftretenden Sachverhalte geschlossen. Der Grad der Richtigkeit der getroffenen Aussage richtet sich nach der Anzahl der einzelnen Betrachtungen und Bestätigungen. Dennoch ist die allgemeine Gültigkeit des aufgestellten Gesetzes dadurch nicht bewiesen. Dazu müßten alle Einzelfälle berücksichtigt werden, was in der Praxis jedoch nicht möglich ist.

Folglich handelt es sich bei der naturwissenschaftlichen Induktion um eine Hypothese, die den Aufstieg von Einzelfällen zu einem allgemeinen Gesetz dokumentiert. Eine solche Art von induktiver Schlußweise ist in den Naturwissenschaften oft in vielen Fällen ausreichend, um korrekte Schlüsse aus unterschiedlichen Sachverhalten zu ziehen.

2. Die vollständige Induktion der Mathematik hingegen hat einen festen Beweischarakter (siehe S.6).

Dabei wird (ähnlich der empirischen Induktion) von einem Einzelfall auf die allgemeingültige Aussage geschlossen, wobei jedoch Einzelfälle vollständig erfaßt werden.

Die vollständige Induktion ist oftmals das einzig mögliche Hilfsmittel, um die allgemeine Gültigkeit einer Gleichung A(n) bzw. eines mathematischen Satzes für alle Zahlen n der Menge der natürlichen Zahlen (n [Abbildung in dieser Leseprobe nicht enthalten] N) zu beweisen.

Das Prinzip des Beweisverfahrens der vollständigen Induktion soll am folgendem Beispiel erläutert werden.

Es sollen die Summen aufeinanderfolgender, ungerader, natürlicher Zahlen ermittelt werden:

Abbildung in dieser Leseprobe nicht enthalten

Folgende geometrische Darstellung soll den Zusammenhang nochmals verdeutlichen:

(a.a.O. Nr.6/ S.44)

Abbildung in dieser Leseprobe nicht enthalten

Auf Grund der erzielten Ergebnisse kann man vermuten, daß sich diese Aufstellung beliebig weit, also für ein unendlich großes n, fortführen läßt, so daß gilt:

Abbildung in dieser Leseprobe nicht enthalten

Die Summe von n aufeinander folgenden, ungeraden Zahlen, wobei n [Abbildung in dieser Leseprobe nicht enthalten] N , beträgt n 2 .

Dieser Schluß auf die allgemeine Gültigkeit ist jedoch nur induktiv, d.h. die Richtigkeit dieser Vermutung wurde bis jetzt nur für die ersten vier Glieder der Zahlenfolge bewiesen und es ist nicht auszuschließen, daß ein beliebiges n -tes Glied (wobei n > 4) die aufgestellte Vermutung widerlegt. ([Abbildung in dieser Leseprobe nicht enthalten] siehe S.8)

Daher bleibt die Gültigkeit der Aussage ungewiß und muß erst bewiesen werden.

Hierbei liegt es nahe, die Richtigkeit der aufgestellten Aussage "Die Summe sn = 1 + 3 + 5 + 7 + ... + (2n - 1) der ersten n ungeraden natürlichen Zahlen beträgt n2" zu vervollständigen.

Dazu wird die allgemeine Nachfolgeeigenschaft der natürlichen Zahlen hinzugezogen: Wenn eine Aussage A für eine bestimmte Zahl n 0 [...] gilt und es außerdem zu zeigen gelingt, daß aus der angenommenen Gültigkeit für eine beliebige Zahl k stets die Gültigkeit für die folgende Zahl (k + 1) folgt, so erreicht man jede natürliche Zahl. (a.a.O. Nr.6/ S.44)

Für den Nachweis der Richtigkeit dieser Implikation wird verlangt:

Wenn für eine beliebige, natürliche Zahl k die Aussage A(k) gilt, dann gilt diese Aussage auch für den Nachfolger (k + 1), kurz: A(k) [Abbildung in dieser Leseprobe nicht enthalten] A(k + 1)

(2.) 1. Induktionsvoraussetzung:

Es wird angenommen, daß A(k) gilt:

Abbildung in dieser Leseprobe nicht enthalten

(2.) 2. Induktionsbehauptung:

Es wird behauptet, daß die Aussage auch für den Nachfolger von k, also für n = (k + 1) gilt.

Daraus folgt:

Abbildung in dieser Leseprobe nicht enthalten

(2.) 3. Induktionsbeweis:

Man erhält die Summe der (k + 1)-ten ungeraden Zahlen durch Addition der nächsten ungeraden Zahl (2k - 1 + 2), also von (2k + 1). Auf diesem Weg gelangt man von sk zu sk + 1.

Abbildung in dieser Leseprobe nicht enthalten

Als Endergebnis erhält man den Ausdruck für sk + 1, so als hätte man die Variable durch (k + 1) ersetzt.

Damit ist die Implikation bewiesen.

Greift man auf die ersten Gedankenschritte dieses Beweises zurück, daß die Aussage A(n) für ein kleines n0, hier n0 = 1, erfüllt ist und fügt sie der Implikation an, so erhält man das Prinzip der vollständigen Induktion, in der Mathematikliteratur auch als "Schluß von n auf n +1" bezeichnet.

Kurz gesagt hängt die Möglichkeit der beschriebenen Schlußweise von zwei Faktoren ab:

1. Die Richtigkeit über die Aussage A(n0) muß bekannt sein
2. Ein allgemeiner Beweis muß geführt werden, daß falls die Aussage A(k) wahr ist, dann auch die darauffolgende Aussage A(k + 1) richtig ist