Facharbeit

im Leistungskurs Mathematik

Thema:

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 (nN).

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:

A(1): s1 = 1

= 1

= 12

A(2): s2 = 1 + 3

= 4

= 22

A(3): s3 = 1 + 3 + 5

= 9

= 32

A(4): s4 = 1 + 3 + 5 + 7

= 16

= 42

...

...

...

Folgende geometrische Darstellung soll den Zusammenhang nochmals verdeutlichen:

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

1 = 12

1 + 3 = 22

1 + 3 + 5 = 32

1 + 3 + 5+ + 7 = 42

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): sn = 1 + 3 + 5 + 7 + ... + (2n - 1) =

(2n - 1) = n2

( wobei n

)

n = 1

Die Summe von n aufeinander folgenden, ungeraden Zahlen, wobei n

, beträgt n2 .

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 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 n0 [...] 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): sk = 1 + 3 + 5 + ... + (2k-1) =

(2n-1) = k2

(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): sk + 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 sk zu sk + 1.

---

sk + 1

=

sk

+ (2k + 1)

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

Nach der binomischen Formel folgt:

sk + 1

= (k + 1)2

Es folgt:

Bezüglich der Voraussetzung, daß A(k)

sk + 1

= sk

+ (2k + 1)

= sk = k2 , läßt sich die Gleichung

= k2

+ (2k + 1)

folgendermaßen umschreiben.

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

---

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:

Wenn 1. A(n) für eine (möglichst kleine) natürliche Zahl n = n0 wahr ist und

2. für eine beliebige natürliche Zahl n = k (k n0) aus der (angenommenen)

Gültigkeit von A(k) stets die Gültigkeit von A(k + 1) folgt,

dann ist A(n) für alle natürlichen Zahlen n n0 wahr.

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

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

vermutet wird bzw. schon vorher bekannt ist.)

Wenn der

erste

Dominostein umfällt, und wenn mit

dem

n-ten

Dominostein auch der

(n+1)-te

umfällt,

dann fallen

alle

Dominosteine um.

(a.a.O.Nr.4/ S.15)

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(n0) 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(n0)

und

Für ein beliebiges k

n0 gilt (A(k)

A(k + 1))

]

A(n) gilt für alle n

n0

Induktionsanfang

Induktionsschluß

(Existenzbeweis)

(Beweis der vollständigen Implikation)

Beweis durch vollständige Induktion

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

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 n0 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
- demonstriert an Hand von Gegenbeispielen

Die folgenden Gegenbeispiele sollen zeigen, daß weder die Verankerung (A(n0) 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.:

Voraussetzung:

n

Behauptung:

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

wobei der Quotient wieder eine natürliche Zahl ist.

Es gilt:

2520 : n = a

,wobei a

Wählt man n = 1 so ist die Behauptung wahr und damit die Existenz einer kleinen

Zahl n0 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

2520 : 11 = 228, 1

a

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

Voraussetzung:

n

Behauptung:

Die Zahl 2 ist Teiler von 3n + 4, d.h.

3n + 4

A(n):

= a

,wobei a

2

Induktionsvoraussetzung:

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

3k + 4

A(k):

= a

,wobei a

2

---

Induktionsbehauptung:

Es wird behauptet, daß die Aussage auch für den Nachfolger von k, also für

n = (k + 1) gilt. Es folgt:

3k+1 + 4

A(k + 1):

= a

,wobei a

2

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:

3k+1 + 4

=

31 3k + 4

= 2 3k + 1 3k + 4

Da

2

3k

durch 2 dividierbar ist und laut der Induktionsvoraussetzung auch

1

3k + 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 3k + 1 3k + 4

3k+1 + 4

=

= a

,wobei a

2

2

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

Dennoch ist die Behauptung, 2 ist ein Teiler von 3n + 4,

falsch !!!

, da es kein n = n0

gibt, für welches die Behauptung gültig wäre. Wählt man z.B. n0 = 1, so folgt:

31 + 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 n0 für

welches die Behauptung erfüllt ist.

Schon am Anfang war sichtbar, daß die Behauptung falsch ist, da 3n 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:

A(n): 1 + nx

(1 + x)n

(der Term ist auf Grund der Voraussetzung positiv)

Beweis:

Voraussetzung:

n ;

x -1 und x 0

Behauptung:

für alle n > 0 gilt:

1 + nx (1 + x)n

1. Induktionsanfang:

Man prüft, ob die BERNOULLIsche Ungleichung für ein kleines n0 erfüllt ist.

Dazu wählt man n0 = 1 und setzt es in die Ungleichung ein.

A(1):

1 + 1x (1 + x)

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 .

Es gelte also:

A(k): 1 + kx

(1 + x)k

2.2. Induktionsbehauptung:

Es wird behauptet, daß die Ungleichung auch für den Nachfolger von k, d.h.

n = k + 1 gilt.

Daraus folgt:

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

(1 + x)k + 1

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:

Man multipliziert die Ungleichung auf

1 + kx (1 + x)k / (1 + x)1

beiden Seiten mit (1 + x)1, wobei laut

Voraussetzung (1 + x)1 0 ist.

Man erhält:

(1 + kx) (1 + x)1 (1 + x)k (1 + x)1

Durch Anwendung der Potenzre-

chengesetze lassen sich die Terme

1 + x + kx + kx2 (1 + x)k + 1

folgendermaßen vereinfachen.

1 + (k + 1)x + kx2

(1 + x)k + 1

Der Term

1 + (k + 1)x + kx2

ist um

kx2 0

den positiven Summanden kx2 größer

als der Ausgangsterm 1 + (k +1)x.

---

Da die Ungleichung auch für den um kx2 größeren Term erfüllt ist, gilt sie erst recht für

1 + (k + 1)x.

1 + (k + 1)x

1 + (k + 1)x + kx2

(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

1 + 3x (1 + x)3

f1(x) = (1 + x)3

f2(x) = 1 + 3x

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 f1(x) f2(x) ist.

Somit kann man unter Verwendung der

BERNOULLIschen Ungleichung die

Entwicklung der Funktionswerte einer Funktion der Form (1 + x)n 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, Differential-

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

---