Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 23. Juli 2019 

Induktion (Mathematik)


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Induktion oder vollständige Induktion oder Schluss von n auf n+1 ist eine Beweismethode die üblicherweise eine Aussage für alle natürlichen Zahlen beweist. Sie funktioniert aber auch für Fälle (siehe unten).

Der Name dieses Beweisverfahrens leitet sich lat. inductio = Hereinführung ab in der Logik meint man damit den Schluss von Sachverhalten auf allgemeine Regeln siehe Induktion (Logik) . Das Verfahren der vollständigen Induktion ist kein induktives sondern ein deduktives Prinzip.

Inhaltsverzeichnis

Definition

Das Beweisverfahren der vollständigen Induktion beruht den Peano-Axiomen für die natürlichen Zahlen N . Eines dieser Axiome (das Induktionsaxiom ) besagt:

Ist X eine Teilmenge von N mit der Eigenschaft dass 0 (bzw. in X liegt und für jedes Element x von X liegt auch x +1 in X dann ist X gleich N .
(Ob man bei 0 oder 1 hängt davon ab ob 0 in N liegt das wird von verschiedenen Mathematikern definiert.)

Um zu beweisen dass eine bestimmte Formel p für jede natürliche Zahl gilt setzt X als die Menge aller natürlichen Zahlen n für die p ( n ) gilt und wendet auf diese Menge Induktionsaxiom an. Man zeigt also p (0) und damit 0 in X sowie p ( n ) => p ( n +1) und damit n in X => n +1 in X . Damit gilt X = N und p gilt für alle natürlichen Zahlen.

Motivation

Hat man eine Aussage die für natürlichen Zahlen gelten soll und es ist möglich oder man hat noch keine Idee Aussage mit einer für alle Zahlen gültigen zu beweisen dann hat man ein Problem: die Anzahl der natürlichen Zahlen unendlich ist man die Wahrheit der Aussage nicht für Zahlen einzeln beweisen.

Beispiel:

Zu zeigen ist dass 1 + + ... + n = n ( n + 1)/2.

Für einzelne Zahlen ist die Formel nachzurechnen:

n =1:

1 = 1
1·(1+1)/2 = 1

n =2:

1 + 2 = 3
2·(2+1)/2 = 3

usw.

Der Überlieferung nach sollte der kleine Gauß in der Schule die Zahlen von bis 100 addieren und überraschte den Lehrer einem richtigen schnellen Ergebnis:

Er bildete 50 Zahlenpaare die jeweils Summe 101 haben: 100+1 99+2 98+3 ... und errechnete 50 * 101 = 5050 Summe. Diese Summenermittlung kann man als gültigen für die spezielle Summenformel mit n=100 ansehen. man kann die Zahlenpaare wirklich auszählen.)

Statt 100 kann hier nun aber n genommen werden. Die Summe der Zahlenpaare zu n+1 und die Anzahl der Zahlenpaare 50 allgemein zu n/2.

Diese Betrachtung gilt sogar wenn n ist. Dann bleibt die mittlere Zahl der ohne Partner. Diese mittlere Zahl die ohne bleibt ist (n+1)/2. Es können zunächst nur Zahlenpaare addiert werden die alle die Summe haben. Am Schluss wird jedoch die übriggebliebene Zahl addiert und es ergibt sich als

((n-1)/2)*(n+1) + (n+1)/2.
Hier wird (n+1) als Faktor nach ausgeklammert und man erhält
((n-1)/2 + 1/2)*(n+1)= (n/2)*(n+1)
Die allgemeine Summenformel lautet daher egal die Zahl der Summanden gerade oder ungerade
1 + 2 + 3 + ... n = (n/2)*(n+1)

Vollständige Induktion ist dabei scheinbar nicht Spiel. An den Stellen jedoch an denen die Summe und die Anzahl der Paare wird wird ein induktiver Schluss durchgeführt denn kann nicht für jedes n die Anzahl der tatsächlich auszählen. Dieser Schluss ist aber kein denn wie im Artikel Induktion (Logik) erläutert können induktive Schlüsse fehlerhaft sein.

Diese Gauß zugeschriebene Begründung der Summenformel erst dann ein mathematischer Beweis wenn sichergestellt dass die beschriebene Umordnung der Zahlen und der Paare für jede natürliche Zahl n ist und das angegebene Ergebnis liefert - das geht sehr gut mit vollständiger Induktion.

Die Idee

Wenn wir wissen dass eine bestimmte sowohl

für n =1 gilt

und

wenn für ein beliebiges n dann auch n+1 gilt

dann ist klar dass sie für alle n gilt.

Damit scheint das Problem auf den Blick nur anders formuliert indem wir die Zahl eben als die vorherige Zahl plus bezeichnen; es sind immer noch unendlich viele Allerdings haben wir tatsächlich etwas gewonnen: indem "der Reihe nach" beweisen können wir beim für n +1 bereits davon ausgehen dass die Aussage für 1 bis n bereits gilt . Das heißt wir können die Formel wir beweisen wollen bereits im Beweis als Voraussetzung für Zahlen unterhalb der Zahl (also unterhalb n +1) verwenden.

Angewandt auf obiges Beispiel sieht das aus:

Wir wollen eine Formel finden die Summe aller ungeraden Zahlen von 1 bis vereinfacht und was wichtiger ist wir wollen Formel beweisen:

 1 = 1 ; 1 + = 4 ; 1 + 3 + = 9 ; 1 + 3 + + 7 = 16  

Vermutung: Die Summe aller ungeraden Zahlen 1 bis n ergibt eine Quadratzahl. Genauer

  • <math>\sum^n_{i=1} 2i-1 = n^2</math>

Das ist zu zeigen. Wenn die stimmt dann müssen verschiedene Dinge zutreffen:

  • <math>\sum^n_{i=1} 2i-1 + (2(n+1)-1)= \sum^{n+1}_{i=1} 2i-1</math>

  • <math>\sum^n_{i=1} 2i-1 + (2(n+1)-1)= n^2 + (2(n+1)-1)</math>

  • <math>\sum^{n+1}_{i=1} 2i-1 = (n+1)^2 </math>

  • <math>n^2 + (2(n+1)-1) = (n+1)^2</math> /* Die */

Das letzte ist die Perle die bewiesen werden muß. Nur die Perle hinzuschreiben als Beweis nicht aus.

  • <math>n^2 + (2(n+1)-1) = (n+1)^2 </math>

  • <math>n^2 + 2n + 2 - 1 n^2 + 2n + 1</math>

  • <math>n^2 + 2n + 1 = n^2 2n + 1</math>

Damit ist die vollständige Induktion für 2i-1 = n^2</math> abgeschlossen und bewiesen.

Angenommen wir haben die Formel bereits zur Zahl n bewiesen. Wir wollen nun die Formel 1 + 2 + 3 + ... n + ( n +1) beweisen.

Die ersten n Summanden bilden ebenfalls eine solche Summe zwar für n was kleiner ist als n +1. Also dürfen wir - nach der dass wir die Formel für n bereits bewiesen haben - selbige hier womit wir erhalten:

1 + 2 + 3 + ... n + ( n +1) = n ( n +1)/2 + ( n +1)

In diesem Ausdruck wird ( n +1) ausgeklammert:

( n +1)*(( n /2)+1)
und dies weiter umgeformt zu
( n +1)*(( n +2)/2)

Das heißt wir haben mit der Voraussetzung dass die zu beweisende Formel für n richtig ist durch Anwendung von richtigen bewiesen dass die Formel dann auch für n +1 gilt denn die erhaltene Formel entspricht Ausgangsformel bei der n nur durch n +1 ersetzt ist.

Zu beachten ist dass hier ein n verwendet wurde. Damit ist der Schritt n zu n +1 hier unabhängig vom konkreten Wert von n allgemein bewiesen.

Der Witz am Induktionsbeweis ist nun wir diese Schritte nicht mehr einzeln durchführen Wir haben ja bereits bewiesen dass der für jedes einzelne n allgemein gilt. Und es ist sofort dass wir jede Zahl erreichen können indem den Schritt nur oft genug anwenden (wenn lange genug zählt dann kann man bis jeder Zahl zählen). Das heißt es muss gezeigt werden dass die zu beweisende Aussage die unterste Zahl gilt (im Beispiel 1 oft jedoch 0) und dass sie wenn bis zu einer Zahl gilt das dann für die nächste Zahl tut.

Bezeichnungen

Den Beweis der Aussage für die Zahl nennt man Induktionsanfang den Beweis für n +1 unter der Annahme ( Induktionsannahme Induktionsvoraussetzung ) dass sie bis n gilt nennt man Induktionsschritt .

Hat man diese beiden Beweisschritte durchgeführt ist die Aussage für alle natürlichen Zahlen In Kurzform:

Wir wählen eine beliebige aber feste Zahl N und zeigen dass die Aussage N wahr ist:

 Die Aussage ist wahr für n 0 (Induktionsanfang) und deshalb für n = (Induktionsschritt) und deshalb für n = 2 ... und deshalb für n = N  
Nach endlich vielen Induktionsschritten gelangt man schließlich zur für N.

Diese Methode ist vergleichbar mit einem Wenn der erste Dominostein fällt und durch fallenden Dominostein ein weiterer umgestoßen wird so schließlich alle Dominosteine.

Tips zur Anwendung

Es kann sich beim Beweis von mitunter als sehr mühsam erweisen beim Induktionsschritt n zu n +1 durch Umformungen die Struktur der Ausgangsformel zu konstruieren . Dies ist jedoch zur Beweisführung unerlässlich. ist es dann manchmal hilfreich das Pferd hinten aufzuzäumen. Beispielsweise ist das Ausmultiplizieren und von Gliedern oftmals leichter zu bewerkstelligen als phantasievolle Aufspalten und Umordnen von Gliedern um ausklammern zu können. Um diesen Umstand zu setzt man in die zu beweisende Formel n +1 für n ein und versucht durch äquivalente Umformungen Ausgangsformel für n zu isolieren. Da die Formel für n laut Voraussetzung gilt ist der Beweis sobald das was bei den äquivalenten Umformungen der isolierten Formel z. B. als Summand als zusätzlicher Faktor entsteht dem entspricht was Induktionsschritt hinzugefügt wird.

Dies ist nicht damit zu verwechseln die zu beweisende Aussage als Voraussetzung verwendet (dies wäre ein wertloser Zirkelschluss ). Wenn die zu beweisende Formel falsch sollte würde entweder auch diese Operation nicht Ziel führen oder die Formel würde den nicht erfüllen oder beides.

Verallgemeinerungen

Als erste Verallgemeinerung kann man als anstatt 0 eine beliebige natürliche Zahl k nehmen. Als Induktionsanfang ist dann der n = k zu betrachten. Alles andere bleibt gleich. Aussage gilt dann eben nicht für alle Zahlen sondern nur für n k .

Eine andere Verallgemeinerung wäre als Induktionsvoraussetzung nur eine Aussage für die Zahl n zu verwenden sondern eine Aussage für Zahlen m mit 0 ≤ m n . D.h. man darf beim Beweis für n +1 annehmen dass die Aussage für alle m n gilt. Dies eröffnet der Beweisführung mehr

Es wird oft als Induktionsschritt nicht n auf n + 1 geschlossen sondern von n - 1 auf n . Auch das ist möglich.

Wenn man zu allgemeineren Mengen übergehen so zeigt sich dass die vollständige Induktion allen Mengen anwendbar ist auf denen eine partielle Ordnung definiert ist wobei keine unendlichen absteigenden auftreten dürfen (weil sonst keine Anfangselemente gefunden können). Eine solche Menge heißt fundierte Menge .

Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen können unendlich und werden). In diesem Fall wird die Methode transfinite Induktion genannt. Sie ist wichtig in der Mengenlehre und der Topologie .



Bücher zum Thema Induktion (Mathematik)

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Induktion_(Mathematik).html">Induktion (Mathematik) </a>