Das Beweisverfahren der vollständigen Induktion und seine Anwendung

Inhaltsverzeichnis

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∈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 ∈ Ν) zu beweisen.

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

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:

Folgende geometrische Darstellung soll den Zusammenhang nochmals verdeutlichen: (a.a.O. Nr.6/ S.44)

1 = 1 ² 1 + 3 = 2 2

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: ∞

A(n): s n = 1 + 3 + 5 + 7 + ... + (2n - 1) = Σ(2n - 1) = n 2

( wobei n ∈ Ν ) n = 1

Die Summe von n aufeinander folgenden, ungeraden Zahlen, wobei 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. (→ 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 s n = 1 + 3 + 5 + 7 + ... + (2n - 1) der ersten n ungeraden natürlichen Zahlen beträgt n ^2" 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) ⇒ A(k + 1)

(2.) 1. Induktionsvoraussetzung:

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

∞

A(k): s k = 1 + 3 + 5 + ... + (2k-1) = Σ(2n-1) = k 2

(k ∈ Ν )

n = k

(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:

∞

A(k + 1): s k + 1 = 1 + 3 + 5 + ...+ (2k - 1) + (2k + 1) = Σ(2n - 1) = (k + 1) 2 n = k+1

(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 s k zu s k + 1 .

s k + 1 = = 1 + 3 + 5 + ...+ (2k - 1) + (2k + 1)

Es folgt:

s k + 1 = s k + (2k + 1) = k ² + (2k + 1)

Als Endergebnis erhält man den Ausdruck für s k + 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 n 0 , hier n 0 = 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(n 0 ) 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

Das Prinzip der vollständigen Induktion

Der Beweis der Gültigkeit einer Aussage A(n) für alle natürlichen Zahlen n beruht auf dem Satz der vollständigen Induktion:

(Anmerkung: Dieses Verfahren läßt sich nur dann anwenden, wenn die zu beweisende Behauptung

vermutet wird bzw. schon vorher bekannt ist.)

Vorgehensweisen bei der praktischen Anwendung:

1. Der erste Schritt der vollständigen Induktion wird als Induktionsanfang oder Induktionsverankerung bezeichnet.

Man beweist, daß eine Aussage A(n) für eine bestimmte, möglichst kleine natürliche Zahl n (meistens 0 oder 1) gültig ist. Damit hat man die Existenz einer natürlichen Zahl bewiesen, für die A(n) wahr ist.

2. Den zweiten Schritt nennt man Induktionsschluß oder Nachfolgevererbung. Dieser gliedert sich in die Induktionsvoraussetzung, Induktionsbehauptung und den Induktionsbeweis.

Als Induktionsvoraussetzung wird die Gültigkeit von A(n) für ein beliebiges n = k festgesetzt.

Die Induktionsbehauptung folgert aus der Voraussetzung die Annahme, daß die Aussage A(n) auch für den Nachfolger von k, also für n = k + 1, gültig ist. Der Induktionsbeweis liefert letztendlich eine Aussage über die Gültigkeit des Schlusses von A(k) auf A(k + 1).

Damit ist bewiesen, daß man durch die Fortsetzung der vollständigen Schlußreihe A(n 0 ) ⇒ A(k) ⇒ A(k + 1) ⇒ A(n) jede natürliche Zahl erreicht und somit die Aussage A(n) allgemeingültig ist.

Schematische Darstellung des Beweisprinzips der vollständigen Induktion

"Verankerung" "Vererbung" [ Es gilt A(n 0 ) und Für ein beliebiges k ≥ n 0 gilt (A(k) ⇒ A(k + 1))] ⇒ A(n) gilt für alle n ≥ n 0

Induktionsanfang (Existenzbeweis)

Das Beweisverfahren der vollständigen Induktion ist ein Sonderfall des "direkten Beweises".

Wie man erkennt, liegt der Vorteil dieses Beweisverfahrens darin, daß die Induktionsvoraussetzung, die Gültigkeit von A(k), nicht direkt rechnerisch bewiesen werden muß. Einen rechnerischen Nachweis erfordert lediglich der Existenzbeweis und die Implikation von A(k) auf A(k + 1).

Ist die zu beweisende Aussage falsch, so tritt ein Widerspruch bei einem der Beweisschritte auf, d.h. es existiert kein n 0 oder die Implikation ist nicht erfüllbar. (siehe S.8) Dennoch kann man umgekehrt aus dem Mißlingen des Beweisverfahrens nicht immer auf die Falschheit der Aussage schließen. Bei komplizierten Fällen kann z.B. eine falsche Grundidee für die notwendigen Umformungen zum Fehlschluß verleiten. Daher gibt es in der Mathematik viele ungelöste Probleme, da man kein Beweisverfahren für die betreffenden Sätze hat finden können.

Der strenge Beweischarakter der vollständigen Induktion

Die folgenden Gegenbeispiele sollen zeigen, daß weder die Verankerung (A(n 0 ) ist wahr) alleine, noch die Vererbung (A(k) ⇒ A(k + 1)) alleine zum Beweis der allgemeinen Gültigkeit einer Gleichung bzw. eines mathematischen Satzes für alle Zahlen n ∈ Ν ausreicht.

Beispiel 1.:

n ∈ Ν Voraussetzung:

Die Zahl 2520 ist durch alle natürlichen Zahlen n (n ≥ 1) teilbar, Behauptung:

Wählt man n = 1 so ist die Behauptung wahr und damit die Existenz einer kleinen Zahl n 0 bewiesen. Der Induktionsanfang (Verankerung) ist erfüllt. Auch für die folgenden Zahlen n = 1, 2, 3, ..., 8, 9, 10 ist die Behauptung wahr. Dies verleitet zu dem Trugschluß, das die aufgestellte Behauptung allgemeingültig sei. Doch schon n = 11 widerlegt diese Annahme, denn ⇒ a ∉ Ν 2520 : 11 = 228, 1 obwohl der Induktionsanfang für die ersten zehn Glieder der Folge gelingt. Damit genügt es nicht die Gültigkeit für ein endliches, wenn auch noch so großes, Anfangsstück einer Folge natürlicher Zahlen zu zeigen. Der Induktionsanfang allein reicht nicht aus, um die allgemeine Gültigkeit der Folge zu beweisen. Es fehlt der Beweis der Implikation, daß aus A(k) ⇒ A(k + 1) folgt, sprich der Induktionsschluß.

Beispiel 2.:

n ∈ Ν Voraussetzung:

Behauptung:

Induktionsvoraussetzung:

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

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

Induktionsbeweis:

Es folgt der Beweis der Implikation, daß aus A(k) ⇒ A(k + 1) folgt.

Durch Anwendung der Potenzregel läßt sich der Zähler folgendermaßen

umschreiben:

Da 2 ⋅ 3 k durch 2 dividierbar ist und laut der Induktionsvoraussetzung auch 1 ⋅ 3 k + 4 durch 2 dividierbar ist, folgt auf Grund des Satzes "Ist jeder Summand einer Summe durch eine Zahl x teilbar, so teilt x auch die Summe" (a.a.O. Nr.6/ S. 48) die Gültigkeit von 2 ⋅ 3 ^k + 1 ⋅ 3 ^k + 4

Damit wurde die Richtigkeit der Implikation A(k) ⇒ A(k + 1) bewiesen.

Dennoch ist die Behauptung, 2 ist ein Teiler von 3 ⁿ + 4, falsch !!!, da es kein n = n ⁰ gibt, für welches die Behauptung gültig wäre. Wählt man z.B. n 0 = 1, so folgt:

3 ¹ + 4 = 7 und 7 : 2 = 3,5 , wobei der Quotient a nicht Element der natürlichen Zahlen (a ∉ Ν) ist.

Es fehlt also der Induktionsanfang, sprich der Beweis der Existenz eines kleinen n 0 für welches die Behauptung erfüllt ist.

Schon am Anfang war sichtbar, daß die Behauptung falsch ist, da 3 ⁿ ein Produkt aus ungeraden Zahlen darstellt und die Addition einer geraden Zahl diese Eigenschaft nicht verändert. Eine ungerade Zahl ist nie durch 2 teilbar, ohne einen Rest zu hinterlassen.

An Hand dieser Gegenbeispiele ist gezeigt worden, daß das Prinzip der vollständigen Induktion einem strengem Beweischarakter unterliegt. Nur der Induktionsanfang (Verankerung) in Verbindung mit dem Implikationsbeweis (Vererbung) führt zu einem korrekten Befund über die allgemeine Gültigkeit einer Aussage A(n).

Beweis der BERNOULLIschen Ungleichung mit Hilfe vollständiger Induktion

Jakob BERNOULLI

Geb. 27.02.1667 Basel Gest. 01.01.1748 Basel J. Bernoulli promovierte in Medizin, entschied sich später jedoch Mathematiker zu werden. 1695 wurde er Professor in Groningen, ab 1705 in Basel. Erstmals befaßte er sich mit der systematischen Darlegung der Differential- und Integralrechnung, fand Methoden zur Integration von Differentialgleichungen und untersuchte Extremalprobleme der Geometrie.

BERNOULLIsche Ungleichung:

Ist x eine reelle Zahl mit x ≥ -1 und x ≠ 0. Dann gilt für alle n ∈ Ν die BERNOULLIsche Ungleichung:

Beweis:

n ∈ Ν ; x≥ -1 und x ≠ 0 Voraussetzung:

Behauptung:

1. Induktionsanfang:

Man prüft, ob die BERNOULLIsche Ungleichung für ein kleines n 0 erfüllt ist. Dazu wählt man n 0 = 1 und setzt es in die Ungleichung ein.

1 + 1x ≤ (1 + x) 1

A(1):

⇔ 1 + x ≤ 1 + x [

Als Ergebnis erhält man eine wahre Aussage, da auf beiden Seiten der Ungleichung der gleiche Term steht.

2. Induktionsschluß:

2.1. Induktionsvoraussetzung:

Es wird angenommen, daß die Behauptung für ein beliebiges n ∈ Ν wahr ist, d.h. n = k .

A(k): 1 + kx ≤ (1 + x) k

Es gelte also:

2.2. Induktionsbehauptung:

Es wird behauptet, daß die Ungleichung auch für den Nachfolger von k, d.h. n = k + 1 gilt.

A(k + 1): 1 + (k + 1)x ≤ (1 + x) k + 1

Daraus folgt:

2.3. Induktionsbeweis:

A(k) ⇒ A(k + 1) Es ist zu zeigen, daß aus der Gültigkeit von A(k) stets die Gültigkeit von A(k + 1) folgt, d.h. daß die BERNOULLIsche Ungleichung für n = k auch für n = k + 1 gilt.

Daraus folgt:

1 + kx ≤ (1 + x) k

Man erhält:

(1 + kx) (1 + x) ¹ ≤ (1 + x) ^k (1 + x) 1

⇔ 1 + x + kx + kx ² ≤ (1 + x) k + 1

⇔ 1 + (k + 1)x + kx 2 ≤ (1 + x) k + 1

Da die Ungleichung auch für den um kx ² größeren Term erfüllt ist, gilt sie erst recht für 1 + (k + 1)x.

⇒ 1 + (k + 1)x ≤ 1 + (k + 1)x + kx ² ≤ (1 + x) k + 1

Damit ist die Gültigkeit der BERNOULLIschen Ungleichung für n = k + 1 bewiesen und somit ist sie für alle n ∈ Ν gültig.

Graphische Darstellung:

Beispiel: n = 3

Betrachtet man die Schaubilder beider Funktionen ab x ≥ -1, so kann man kann erkennen, daß abgesehen vom Schnittpunkt S(0/1), den Funktionen bei gleichen x-Werten unterschiedliche Funktionswerte zugeordnet werden, wobei f 1 (x) ≥ f 2 (x) ist. Somit kann man unter Verwendung der BERNOULLIschen Ungleichung die Entwicklung der Funktionswerte einer Funktion der Form (1 + x) ⁿ für x gegen Unendlich im Vergleich zu (1 + nx) schätzen.

Schlußwort

Wie die Facharbeit aufzeigt, ist das Prinzip der vollständigen Induktion ein wichtiges Mittel, um die Gültigkeit einer Aussage für alle natürlichen Zahlen n zu beweisen. Auf Grund seiner Struktur bietet es eine logische Schlußfolgerung von einem Einzelfall auf die allgemeine Gültigkeit einer Feststellung an. Ferner sind seine Anwendungsgebiete vielfältig und dienen zum Beweis mathematischer Sätze der Algebra, Differentialrechung (z.B. den Ableitungsregeln), sowie der Geometrie.

In der Elementarmathematik wird das Beweisverfahren der vollständigen Induktion meistens angewandt, ohne dies besonders hervorzuheben. Ein fortlaufender, gültiger Zusammenhang wird oftmals mit "usw." angedeutet.

Bei komplizierten Beweisen ist jedoch ein ausdrücklich aufgeführter Gebrauch des Induktionsschlusses vorauszusetzen.

Abschließend wäre noch anzumerken, daß das Beweisverfahren der "vollständigen Induktion", trotz seines Namens, ein deduktives Beweisverfahren ist, wo man von Axiomen zu beweisbaren Sätzen gelangt. Im Allgemeinen bildet die Deduktion die Grundlage der exakten Beweisführung, insbesondere in der Mathematik.

Quellenverzeichnis

1. Courant, Richard:

Vorlesungen über Differential- und Integralrechnung Bd. 1 Springer Verlag, 1971

2. Haarmann, Kusch:

Mathematik für Fachoberschulen und Fachgymnasien Girardet Verlag, 1980

3. Hilbert, Alfred:

Mathematik Grundlagenwissen Bechtermünz Verlag, 1997

4. Scheid, Harald:

Abiturwissen Analysis Ernst Klett Verlag, 1989

5. Schmieder, Gerald:

Analysis: Eine Einführung für Mathematiker und Informatiker Vieweg Verlag, 1994

6. Weber, Karlheinz / Zillmer, Wolfgang: Mathematik Leistungskurs Paetec Verlag, 1996

7. Bertelsmann Universallexikon Bd.2 Bertelsmann Verlag, 1994