|
Die Induktion liefert wie in Kapitel 2 erläutert keinen eindeutigen Beweisschluss. In der Mathematik ist man jedoch bestrebt, durch deduktive Methoden eindeutige Aussagen zu formulieren. Eine Möglichkeit, eine Induktionsvermutung über die natürlichen Zahlen zu beweisen, bietet das auf den Eigenschaften der natürlichen Zahlen (siehe Kpt.4) beruhende Verfahren \"Vollständige Induktion\".
3.1 Vorstellung des Verfahrens
Grundlage des Verfahrens ist eine durch Induktion gewonnene, aber noch nicht bewiesene Aussage, von der man annimmt, dass sie für alle natürlichen Zahlen gilt. Der Beweis folgt in zwei Schritten:
1. Induktionsanfang: Man bestätigt die Vermutung für eine natürliche Zahl (der Einfachheit halber nimmt man die möglichst kleinste Zahl; die unterste Zahl, von der an ab der zu beweisende Satz zutrifft) und zeigt somit, dass es überhaupt eine natürliche Zahl gibt, für die die Behauptung gilt.
2. Induktionsschritt: Man geht von der Induktionsvoraussetzung aus, dass die vermutete Gesetzmäßigkeit für eine beliebige Zahl k gilt. Daraufhin beweist man durch algebraische Umformungen, geometrische Überlegungen oder logische Schlüsse die Induktionsbehauptung, nämlich dass die Gesetzmäßigkeit auch für die nachfolgende Zahl k+1 gilt.
Durch diese beiden Schritte wurde gezeigt, dass die Aussage für alle natürlichen Zahlen gilt.
3.2 Beispiel für eine Anwendung der vollständigen Induktion
Beispiel: Die Summe der ersten n ungeraden Zahlen
Vorüberlegung: Durch einfaches Ausprobieren mit kleinen Zahlen ergibt sich folgendes Schema:
n Summe (1+3+5++ (2n-1) )
1 1
2 1 + 3 = 4
3 1 + 3 + 5 = 9
4 1 + 3 + 5 + 7 = 16
Die Beobachtung der Ergebnisse lässt eine Vermutung aufkommen, nämlich dadurch, dass diese Zahlen einem eine bekannte \"Kategorie\" suggerieren sie sind den ersten Quadratzahlen n2 jeweils gleich.
Die Vermutung wurde hier durch eine Induktion gewonnen (und ist damit noch nicht bewiesen!), Grundlage dafür war die Beobachtung der Analogie zwischen der Summe der ersten n ungeraden Zahlen und den ersten Quadratzahlen n2 .
Behauptung An : Die Summe der ersten n ungeraden Zahlen entspricht n2. An gilt für alle natürlichen Zahlen n * .
1.Schritt: Induktionsanfang: Dieser Schritt ist eigentlich durch die Wertetabelle (s.o.) schon mehrmals ausgeführt worden, denn die Behauptung ist für n = 1, 2, 3, 4 bereits bestätigt worden. A1 (bzw. A2 , A3 oder A4) ist also wahr.
2.Schritt: Induktionsschritt: Die Induktionsvoraussetzung Ak ist in diesem Fall: Es gibt eine natürliche Zahl k , die von 0 (diese Einschränkung war schon in der Behauptung erfolgt) und von 1 (bzw. 2, 3 oder 4) verschieden ist, und für die die obige Vermutung als wahr vorausgesetzt ist.
Diese Aussage ist nicht bewiesen, sie ist nur die allgemeine Fassung des Ausdrucks im Induktionsanfang (dort wurden konkrete Zahlen eingesetzt) und wird im Induktionsschritt als Grundlage der nachfolgenden Induktionsbehauptung Ak+1 verwendet.
Nun folgt der eigentliche Beweis:
Induktionsvoraussetzung Ak: 1 + 3 + 5 + ... + (2k-1) = k2
Induktionsbehauptung Ak+1: 1+ 3+ 5 + ...+ (2k-1) + (2(k+1)-1) = (k+1)2
Beweis:
Somit wurde bewiesen, dass die Aussage unter der Voraussetzung, dass sie für die beliebige Zahl k gilt auch für deren Nachfolger k+1 zutrifft. Im Induktionsanfang wurde die Gültigkeit der Aussage für einige Beispielszahlen schon gezeigt; aus dem Induktionsschritt folgt nun, dass die Aussage ebenfalls für den Nachfolger einer beliebigen Beispielszahl zutrifft. Also ist die Aussage für alle natürlichen Zahlen (die Null natürlich ausgenommen) wahr.
Also gilt An für alle n * !
[Quelle Kpt.3.1-2: (1) Hahn/Dzewas, Analysis Leistungskurs, Seite 370-374]
3.3 Die \"Vollständige Induktion\" als Beweis
Die Bezeichnung vollständige Induktion ist eigentlich für dieses Verfahren unpassend, da eine Induktion nur einen plausiblen Schluss liefert. Durch die vollständige Induktion wird jedoch eine Behauptung durch einen eindeutigen Beweisschluss verifiziert. Das Beweisverfahren stellt demnach eine Form der Deduktion dar. Trotzdem besitzt sie auch induktiven Charakter!
Durch die Zweiteilung des Verfahrens wird deutlicher, wo Unterschiede liegen: Im 1. Schritt oder Induktionsanfang wird eine durch Induktion hergeleitete Aussage gemacht, zu der man durch eine Analogiebeobacht-ung (beim Ausprobieren verschiedener Zahlen) gelangt ist; das Einsetzen der (möglichst kleinen) Beispielszahl ist jedoch ein deduktiver Beweis des behaupteten Satzes für diese spezielle natürliche Zahl.
Im 2. Schritt oder Induktionsschritt folgt dann der ebenfalls deduktive Beweis der Behauptung, \"daß aus der Gültigkeit der Behauptung für n auch die Richtigkeit für n+1 folgt. Aus diesem Grunde wird diese Methode gelegentlich \'Schluss von n auf n+1\' genannt.\"
Insgesamt lässt sich sagen, dass mit dieser Beweismethode eine Induktionsaussage deduktiv bewiesen wird, die Induktion wird (mathematisch) vervollständigt!
Eine Veranschaulichung dafür, dass beide Schritte der vollständigen Induktion zwingend notwendig sind, ist eine Reihe aufgestellter Domino Steine, bei denen eine Kettenreaktion ausgelöst wird. Hier muss ein Stein angestoßen sein, der dann den nächsten Stein umstößt. Ist dies nicht der Fall, so fällt gar nichts um. Wenn irgendein Stein in der Reihe die Bewegung nicht weitergibt, dann kommt die Kettenreaktion zum Stillstand.
|
