Oberstufe: Differential- und Integralrechnung

Oberstufenskript Differential- und Integralrechnung für Grund- und Leistungskurse von Jürgen Rohde

zurück zum INHALT

 2.4 Punkt-Steigungsform, Zwei-Punkteform der Geradengleichungen

3. Das Beweisverfahren der vollständigen Induktion
 

Ein Teilgebiet der Philosophie, die Erkenntnistheorie, befasst sich mit der Frage, wie der Mensch wahre Aussagen gewinnen und ihre Wahrheit sichern kann. Zwei wesentliche Methoden sind die Induktion und die Deduktion.
Die erstere bedeutet den Schluss vom Besonderen auf das Allgemeine, ein in den Naturwissenschaften sehr geläufiges Verfahren; die letztere umgekehrt den Schluss vom Allgemeinen auf das Besondere, wie z.B. für  a, b    a + b = b + a ; also   3 + 4 = 4 + 3 .
Offensichtlich ist die Deduktion das der Mathmatik zuzuordnende angemessene Erkenntnisverfahren. Das induktive Verfahren kann offenbar nicht ohne Zweifel zu sicheren Aussagen führen.
Der Name "vollständige Induktion" ist im Grunde widerspruchsvoll und in der Sache auch unberechtigt. Wie zu sehen sein wird, handelt es sich in Wahrheit um ein deduktives Verfahren.

1. Beispiel:
Es sei h > -1 und h 0 . Dann gilt

	( 1 + h )n > 1 + n h	Bernoullische Ungleichung
	für alle natürlichen Zahlen n 2 .

Wie kann diese Aussage bewiesen werden? Eigentlich handelt es sich doch um so viele Aussagen, wie es natürliche Zahlen gibt. Sie alle einzeln zu beweisen, reicht menschliche Zeit nicht aus. Wir brauchen eine endliche Beweisstrategie.
Es liegt nahe, die Ungleichung für n = 2 zu beweisen:
    ( 1 + h )² = 1 + 2h + h²  >  1 + 2h    (weil h² > 0 )
Für n = 3 und folgende könnte man analog verfahren, aber wir bekämen damit keinen Hinweis auf eine erfolgreiche Beweisstrategie.
Aussichtsreicher ist folgende Strategie:
Wir wissen bereits:
    ( 1 + h )²  >  1 + 2h
Wenn wir diese Ungleichung mit ( 1 + h ) mutiplizieren, folgt
    ( 1 + h )³  >  ( 1 + 2h ) · ( 1 + h ) = 1 + 3h + 2h²  >  1 + 3h   (warum ist ( 1 + h ) > 0 ?)
also ( 1 + h )³  >  1 + 3h .
Ganz analog folgt hieraus
    ( 1 + h )⁴  >  1 + 4h .
So können wir offenbar fortfahren. Aus der Gültigkeit der Ungleichung für eine natürliche Zahl folgt deren Gültigkeit für die nachfolgende natürliche Zahl. Wir können dies im Beispiel allgemeingültig zeigen:
aus   ( 1 + h )ⁿ  >  1 + nh .
folgt durch Multiplikation mit  1 + h > 0  und  wegen h² > 0
    ( 1 + h )^{n + 1}  >  ( 1 + nh) · ( 1 + h ) = 1 + ( n + 1 ) h + nh²  >  1 + ( n + 1 ) h ,
d.i. die Aussage für  n + 1 .
Damit ist die Gültigkeit der Ungleichung für alle n ( n 2 ) plausibel. Die Annahme, sie sei von irgendeiner natürlichen Zahl n₀ ab falsch, führt nun zum Widerspruch (wie ?).

Die vorstehende Erörterung legt folgende Beweisstrategie nahe:

1.	Induktionsanfang	(auch Induktionsverankerung)
	Die Aussage wird für eine 1. natürliche Zahl n0 (hier n0 = 2 ) bewiesen.
2.	Schluss von n auf (n + 1)	(auch Vererbungsschritt genannt)
	Für alle natürlichen Zahlen n n0 wird bewiesen: Wenn die Aussage für n richtig ist, so auch für den Nachfolger n + 1 .
Wenn 1. und 2. durchgeführt sind, ist die Aussage für alle n n0 richtig.

2. Beispiel

Sn =	1   1·2	+	1   2·3	+	1   3·4	+ · · · +	1     n (n + 1)	=	n    n + 1	für alle n

Beweis:
  1. Induktionsanfang      Für n = 1 ist zu beweisen

S1 =

1   1·2

=

1   1 + 1

,   was trivialerweise richtig ist.

  2. Schluss von n auf n + 1

Zu beweisen ist: Wenn   Sn =

n    n + 1

,   so   Sn+1 =

n + 1 n + 2

( n )

Sn+1 = Sn +

1       (n+1)(n+2)

=

n    n + 1

+

1       (n+1)(n+2)

=

n(n + 2) + 1   (n+1)(n+2)

=

n² + 2n + 1 (n+1)(n+2)

=

(n + 1) 2 (n+1)(n+2)

=

n + 1 n + 2

Also ist die Formel für alle n richtig.

3. Beispiel
Für alle n 5 gilt   2ⁿ > n² .
Beweis:
  1. Induktionsanfang      2⁵ = 32 > 5² = 25 ist richtig.
  2. Schluss von n auf n + 1

Für alle n 5 ist zu beweisen:    Wenn 2ⁿ > n² , so auch 2ⁿ⁺¹ > (n + 1)² .
Zum Beweis multiplizieren wir die Ungleichung mit der für n 5 sicher richtigen Ungleichung

2 >

(n + 1)    n2

und erhalten - wie verlangt -   2n+1 > (n + 1)2,

Nach diesen Beispielen können wir das Beweisverfahren der vollständigen Induktion abstrakt formulieren.

	Das Axiom von der vollständigen Induktion
	sei Teilmenge von (Menge der natürlichen Zahlen) mit den folgenden zwei Eigenschaften:
	1.   2.	1   Für alle n gelte: falls n , so auch (n + 1) .   Dann ist = .

Der Mathematiker Peano hat die Menge der natürlichen Zahlen durch 5 Axiome charakterisiert. Das 5. ist das sog. Induktionsaxiom, wie hier angegeben.
Seine Plausibilität erlaubt die Wahl als Axiom.
Nicht alle Mathmatiker haben sich damit einverstanden erklären können. Das Axiom ist ja von nicht ganz einfacher Struktur. Sie haben, wie z.B. Erhard Schmidt, nach ihrer Meinung einfachere Axiomensysteme für die Menge der natürlichen Zahlen aufgestellt. In einem solchen System ist das "Induktionsaxiom" ein beweisbarer Lehrsatz, womit sein deduktiver Charakter klarer hervortritt.

Bermerkungen:

1. Keiner der beiden Beweisschritte ist überflüssig.
Z.B. liefert der Term  n² + n + 41  für alle n = 1; 2; 3; ...; 39 Primzahlen, nicht jedoch für n = 40 oder 41.
Andererseits ist der Schluss von n auf n + 1 richtig durchführbar, auch wenn der Induktionsanfang falsch ist. Wenn z.B. (2n - 1) eine gerade Zahl ist, so auch [2(n + 1) - 1] = (2n + 2 - 1) = (2n -1) + 2 .

2. Der Schluss von n auf n + 1 wird leicht und allzu häufig logisch falsch verstanden. Der Einfachheit halber bezeichnen wir die zu beweisenden Aussagen mit A_n.
Der Schluss von n auf n + 1 hat dann zu beweisen:

Für alle n gilt:     Wenn A_n gilt, dann gilt A_n+1 .
NICHT jedoch: Wenn für alle n   A_n gilt, dann gilt für alle (n + 1)   A_n+1 .

weiter zu    4. Ganzrationale Funktionen  

 zurück zu MATHEMATIK Übersicht