Induktion (Mathematik)

Zum Forum
Passwort vergessen? Noch keinen Account?

lexikon

Hauptseite

Zufälliger Artikel

Diskussion

Diskussion : Induktion (Mathematik)

Links

Forum

Portale

Reisen

Versicherung

Inhaltsverzeichnis

Hauptmenü

Home

Bildung

Wissen

--------------------------

Reisen

Lexikon

Versicherung

Suchen

News

Treffpunkt

Chat

Forum

Suche

Schnellsuche

Sitemap

Kontakt

Impressum

Induktion (Mathematik)

Stichpunkte

Allgemein
	die Ã¼blicherweise eine Aussage fÃ¼r alle natÃ¼rlichen Zahlen beweist
	Induktion oder vollstÃ¤ndige Induktion oder Schluss von n auf n+1 ist eine Beweismethode
	Sie funktioniert aber auch fÃ¼r allgemeinere FÃ¤lle (siehe unten)
	in der Logik meint man damit den Schluss von speziellen Sachverhalten auf allgemeine Regeln
	siehe Induktion (Logik)
	Der Name dieses Beweisverfahrens leitet sich von lat. inductio (= HereinfÃ¼hrung) ab
	Das Verfahren der vollstÃ¤ndigen Induktion ist jedoch kein induktives
	"Verbergen") 1 Definition 2 Motivation 2.1 Beispiel 3 Die Idee 4 Anderes Beispiel: Summe der ungeraden Zahlen 5 Bezeichnungen 6 Tipps zur Anwendung 7 Anwendungen 8 Verallgemeinerungen und Variationen 8.1 Beweis fÃ¼r fast alle natÃ¼rlichen Zahlen 8.2 Verwendung mehrerer VorgÃ¤nger 8.3 VorwÃ¤rts-rÃ¼ckwÃ¤rts-Induktion 8.4 Sonstige [Bearbeiten]
	sondern ein deduktives Prinzip. Inhaltsverzeichnis showTocToggle("Anzeigen"
Definition
	Das Beweisverfahren der vollstÃ¤ndigen Induktion beruht auf den Peano-Axiomen fÃ¼r die natÃ¼rlichen Zahlen <math>mathbb{N}<math>
	dass 0 (bzw
	Eines dieser Axiome (das Induktionsaxiom) besagt: Ist K eine Teilmenge von <math>mathbb{N}<math> mit den Eigenschaften
	dass eine bestimmte logische Formel p(n) fÃ¼r jede natÃ¼rliche Zahl n gilt
	setzt man K als die Menge aller natÃ¼rlichen Zahlen k
	und wendet auf diese Menge das Induktionsaxiom an
	fÃ¼r die p(k) gilt
	ob 0 als Element von <math>mathbb{N}<math> gezÃ¤hlt wird; das wird je nach ZweckmÃ¤ÃŸigkeit unterschiedlich definiert.) Um zu beweisen
	hÃ¤ngt davon ab
	1) in K liegt und fÃ¼r jedes Element k von K auch k+1 in K liegt
	dann ist K gleich <math>mathbb{N}<math>. (Ob man bei 0 oder 1 beginnt
	und damit 1 in K
	sowie p(k) => p(k+1)
	Man zeigt also p(1)
	dass fÃ¼r k in K auch k+1 in K liegt
	und damit
	Damit gilt K = <math>mathbb{N}^+<math>
	und p(n) gilt fÃ¼r alle natÃ¼rlichen Zahlen <math>nge 1<math>. [Bearbeiten]
Motivation
	dann hat man ein Problem: Da die Anzahl der natÃ¼rlichen Zahlen unendlich ist
	kann man die Wahrheit der Aussage nicht fÃ¼r alle Zahlen einzeln beweisen. [Bearbeiten]
	und es ist nicht mÃ¶glich
	die Aussage mit einer fÃ¼r alle Zahlen gÃ¼ltigen Rechnung zu beweisen
	oder man hat noch keine Idee
	Hat man eine Aussage
	die fÃ¼r alle natÃ¼rlichen Zahlen gelten soll
Beispiel
	Zu zeigen ist
	dass <math>1+2+...+n = frac{n(n+1)}{2}<math>
	FÃ¼r einzelne Zahlen ist die Formel leicht nachzurechnen: <math>n = 1<math>: <math>1 = frac{1(1+1)}{2}<math> <math>n = 2<math>: <math>1 + 2 = 3 = frac{2(2+1)}{2}<math> usw. [Bearbeiten]
Die Idee
	und
	dann auch fÃ¼r n = k+1 gilt
	wenn fÃ¼r ein beliebiges n = k
	dass eine bestimmte Aussage sowohl fÃ¼r n = 1 gilt
	Wenn wir wissen
	dass sie fÃ¼r alle n gilt
	dann ist klar
	Damit scheint das Problem auf den ersten Blick nur anders formuliert
	indem wir die nÃ¤chste Zahl eben als die vorherige Zahl plus 1 bezeichnen; es sind immer noch unendlich viele Zahlen
	Allerdings haben wir tatsÃ¤chlich etwas gewonnen: indem wir "der Reihe nach" beweisen
	dass die Aussage fÃ¼r n=1 bis n=k bereits gilt
	kÃ¶nnen wir beim Beweis fÃ¼r n=k+1 bereits davon ausgehen
	wir kÃ¶nnen die Formel
	die wir beweisen wollen
	bereits im Beweis als Voraussetzung fÃ¼r Zahlen unterhalb der aktuellen Zahl (also unterhalb k+1) verwenden
	Das heiÃŸt
	wir haben die Formel bereits bis zur Zahl n=k bewiesen
	Angewandt auf obiges Beispiel sieht das so aus: Angenommen
	also die Summe 1 + 2 + 3 + ... + k + (k+1) berechnen
	Wir wollen nun die Formel fÃ¼r n=k+1 beweisen
	was kleiner ist als k+1
	Die ersten k Summanden bilden ebenfalls eine solche Summe
	und zwar fÃ¼r k
	wir haben mit der gemachten Voraussetzung
	womit wir erhalten: <math>1 + 2 + 3 + ... + k + (k+1) = frac{k(k+1)}{2} + (k+1)<math> In diesem Ausdruck wird (k+1) ausgeklammert: <math>= (k+1) cdot left(frac{k}{2}+1 right)<math> und dies weiter umgeformt zu <math>= (k+1) cdot frac{k+2}{2}<math> Das heiÃŸt
	bei der n nur durch k+1 ersetzt ist
	dass die Formel dann auch fÃ¼r n=k+1 gilt
	dass die zu beweisende Formel fÃ¼r n=k richtig ist
	durch Anwendung von richtigen Rechenschritten bewiesen
	denn die erhaltene Formel entspricht der Ausgangsformel
	Also dÃ¼rfen wir - nach der Voraussetzung
	dass wir die Formel fÃ¼r n=k bereits bewiesen haben - selbige hier anwenden
	dass k beliebig gewÃ¤hlt werden darf
	Zu beachten ist
	Damit ist der Schritt von k zu k+1 hier unabhÃ¤ngig vom konkreten Wert von k allgemein bewiesen
	Der Witz am Induktionsbeweis ist nun
	dass der Schritt fÃ¼r jedes einzelne k allgemein gilt
	dass wir diese Schritte nicht mehr einzeln durchfÃ¼hren mÃ¼ssen: Wir haben ja bereits bewiesen
	dass wir jede Zahl erreichen kÃ¶nnen
	indem wir den Schritt nur oft genug anwenden (wenn man lange genug zÃ¤hlt
	dann kann man bis zu jeder Zahl zÃ¤hlen - das ist die umgangssprachliche Formulierung des Induktionsaxioms)
	Und es ist sofort klar
	das dann auch fÃ¼r die nÃ¤chste Zahl tut
	dass die zu beweisende Aussage fÃ¼r die unterste Zahl gilt (im Beispiel 1
	und dass sie
	sehr oft jedoch 0)
	es muss nur gezeigt werden
	Das heiÃŸt
	wenn sie bis zu einer Zahl gilt
	In der Praxis wird Ã¼blicherweise fÃ¼r n und k der gleiche Buchstabe n gewÃ¤hlt
	so sieht es so aus
	Das ist kein Problem
	als ob die zu beweisende Aussage als Voraussetzung verwendet wÃ¼rde; dies wÃ¤re aber ein wertloser Zirkelschluss
	solange man sich der unterschiedlichen Bedeutung von n in "p(n) gilt fÃ¼r alle natÃ¼rlichen Zahlen n" in der zu beweisenden Aussage und "p(n) gilt fÃ¼r ein konkretes n=k" in der Induktionsvoraussetzung bewusst ist. Ãœbersieht man diesen Unterschied
	wÃ¼rde entweder der Induktionsschritt nicht zum Ziel fÃ¼hren oder die Formel wÃ¼rde den Induktionsanfang nicht erfÃ¼llen oder beides. [Bearbeiten]
	Wenn die zu beweisende Formel falsch sein sollte
Anderes Beispiel: Summe der ungeraden Zahlen
	die die Summe aller ungeraden Zahlen von 1 bis n vereinfacht und
	wir wollen diese Formel beweisen: 1 = 1; 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16 Vermutung: Die Summe aller ungeraden Zahlen von 1 bis n ergibt eine Quadratzahl
	Wir wollen eine Formel finden
	was wichtiger ist
	Genauer gesagt: <math>sum^n_{i=1} (2i-1) = n^2<math> Das ist zu zeigen
	mÃ¼ssen zwei Dinge gezeigt werden: <math>sum^1_{i=1} (2i-1) = 1^2 = 1<math> Wenn <math>sum^n_{i=1} (2i-1) = n^2 <math>
	Um diese Formel zu beweisen
	so ist <math>sum^{n+1}_{i=1} (2i-1) = (n+1)^2<math> Dies zeigt man durch die Gleichung <math>sum^{n+1}_{i=1} (2i-1) = sum^n_{i=1} (2i-1) + 2(n+1)-1 = n^2 + 2(n+1)-1 = n^2 + 2n +1 = (n+1)^2<math>
	Die binomische Formel liefert die letzte Gleichheit
	Damit ist die vollstÃ¤ndige Induktion fÃ¼r <math>sum^n_{i=1} (2i-1) = n^2<math> abgeschlossen und bewiesen. [Bearbeiten]
Bezeichnungen
	dass sie bis n gilt
	Induktionsvoraussetzung)
	den Beweis fÃ¼r n+1 unter der Annahme (Induktionsannahme
	Den Beweis der Aussage fÃ¼r die erste Zahl nennt man Induktionsanfang
	nennt man Induktionsschritt
	dann ist die Aussage fÃ¼r alle natÃ¼rlichen Zahlen bewiesen
	Hat man diese beiden Beweisschritte durchgefÃ¼hrt
	dass die Aussage fÃ¼r N wahr ist: Die Aussage ist wahr fÃ¼r n = 0 (Induktionsanfang) und deshalb fÃ¼r n = 1 (Induktionsschritt) und deshalb fÃ¼r n = 2 (Induktionsschritt) ... und deshalb fÃ¼r n = N (Induktionsschritt) Nach endlich vielen Induktionsschritten gelangt man schlieÃŸlich zur Aussage fÃ¼r N
	In Kurzform: Wir wÃ¤hlen eine beliebige aber feste natÃ¼rliche Zahl N und zeigen
	Diese Methode ist vergleichbar mit einem Dominoeffekt: Wenn der erste Dominostein fÃ¤llt und durch jeden fallenden Dominostein ein weiterer umgestoÃŸen wird
	so fallen schlieÃŸlich alle Dominosteine. [Bearbeiten]
Tipps zur Anwendung
	beim Induktionsschritt von n zu n+1 durch Umformungen die Struktur der Ausgangsformel neu zu konstruieren
	Es kann sich beim Beweis von Summenformeln mitunter als sehr mÃ¼hsam erweisen
	Dies ist jedoch zur BeweisfÃ¼hrung unerlÃ¤sslich
	Da ist es dann manchmal hilfreich
	das Pferd von hinten aufzuzÃ¤umen
	Beispielsweise ist das Ausmultiplizieren und Zusammenfassen von Gliedern oftmals leichter zu bewerkstelligen als das phantasievolle Aufspalten und Umordnen von Gliedern
	um etwas ausklammern zu kÃ¶nnen
	setzt man in die zu beweisende Formel n+1 fÃ¼r n ein und versucht
	Um diesen Umstand zu nutzen
	durch Ã¤quivalente Umformungen die Ausgangsformel fÃ¼r n zu isolieren
	ist der Beweis gefÃ¼hrt
	was bei den Ã¤quivalenten Umformungen auÃŸer der isolierten Formel z
	sobald das
	Da die Formel fÃ¼r n laut Voraussetzung gilt
	B. als Summand oder als zusÃ¤tzlicher Faktor entsteht
	was beim Induktionsschritt hinzugefÃ¼gt wird. [Bearbeiten]
	dem entspricht
Anwendungen
	Baut man die natÃ¼rlichen Zahlen auf den Peano-Axiomen auf
	Kommutativgesetz und Distributivgesetz fÃ¼r die Addition und Multiplikation natÃ¼rlicher Zahlen mit vollstÃ¤ndiger Induktion bewiesen
	so werden die arithmetischen Grundgesetze wie Assoziativgesetz
	komplexen Zahlen)
	Leipzig 1930
	rationalen
	Eine ausfÃ¼hrliche Ausarbeitung dieser Beweise findet sich in Edmund Landau: Grundlagen der Analysis (Das Rechnen mit ganzen
	irrationalen
	Weitere wichtige mathematische SÃ¤tze
	sind beispielsweise der Binomische Lehrsatz und die Bernoullische Ungleichung. [Bearbeiten]
	die Ã¼blicherweise mit Induktion bewiesen werden
Verallgemeinerungen und Variationen
	[Bearbeiten]
Beweis fÃ¼r fast alle natÃ¼rlichen Zahlen
	die nicht fÃ¼r alle natÃ¼rlichen Zahlen
	sondern nur fÃ¼r alle Zahlen ab einem gewissen Startwert gelten
	Der Induktionsbeweis ist auch fÃ¼r Aussagen mÃ¶glich
	<math>2n^2 =n^2+n^2ge n^2+3n > n^2+2n+1=(n+1)^2<math> fÃ¼r <math>nge 3<math>. Die Ungleichung ist allerdings fÃ¼r <math>n=3<math> falsch
	gilt aber fÃ¼r <math>n=4<math>; der Induktionsbeweis zeigt also die GÃ¼ltigkeit der Ungleichung fÃ¼r <math>nge 4<math>
	So lÃ¤sst sich beispielsweise fÃ¼r die Ungleichung <math>2^nge n^2<math> der Induktionsschritt fÃ¼r <math>nge 3<math> durchfÃ¼hren: <math>2^{n+1}=2cdot 2^nge 2n^2<math> laut Induktionsvoraussetzung
	die durch den Induktionsbeweis nicht abgedeckt sind
	Die endlich vielen FÃ¤lle
	kÃ¶nnen einzeln untersucht werden. [Bearbeiten]
Verwendung mehrerer VorgÃ¤nger
	fÃ¼r den Beweis der Aussage fÃ¼r n+1 die GÃ¼ltigkeit sowohl fÃ¼r n als auch fÃ¼r n-1 (oder fÃ¼r noch mehr VorgÃ¤nger) vorauszusetzen
	Manchmal ist es notwendig
	da ja beispielsweise fÃ¼r den Induktionsschritt fÃ¼r n=1 auch die Voraussetzung fÃ¼r n=-1 benÃ¶tigt wÃ¼rde
	Der Induktionsanfang muss dann allerdings fÃ¼r mehrere Startwerte (also z.B. n=0 und n=1) durchgefÃ¼hrt werden
	Ein Beispiel wÃ¤re der Beweis der Formeln von Binet <math>f_n=frac{1}{sqrt{5}}(a^n-b^n)<math> mit a = <math>frac{1+sqrt{5}}{2}<math> und b = <math>frac{1-sqrt{5}}{2}<math> fÃ¼r die Fibonacci-Folge <math>f_n<math>. [Bearbeiten]
VorwÃ¤rts-rÃ¼ckwÃ¤rts-Induktion
	Eine andere Variante ist die "VorwÃ¤rts-rÃ¼ckwÃ¤rts-Induktion"
	indem z.B. von n auf 2n geschlossen wird; danach werden die LÃ¼cken mit einem RÃ¼ckwÃ¤rstsschritt geschlossen
	Dabei wird in einem VorwÃ¤rtsschritt die Aussage fÃ¼r beliebig groÃŸe Zahlen bewiesen
	in dem z.B. aus der GÃ¼ltigkeit fÃ¼r n die GÃ¼ltigkeit fÃ¼r n-1 bewiesen wird
	Analyse algebrique
	Paris 1821 zum Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet. [Bearbeiten]
	premier partie
	in Cours d'analyse de l'Ecole Royale Polytechnique
	Diese Technik wurde beispielsweise von Augustin Louis Cauchy
Sonstige
	Eine andere Verallgemeinerung wÃ¤re
	als Induktionsvoraussetzung nicht nur eine Aussage fÃ¼r die Zahl n zu verwenden
	sondern eine Aussage fÃ¼r alle Zahlen m mit 0 â‰¤ m â‰¤ n
	dass die Aussage fÃ¼r alle m â‰¤ n gilt
	D.h. man darf beim Beweis fÃ¼r n+1 annehmen
	Dies erÃ¶ffnet der BeweisfÃ¼hrung mehr MÃ¶glichkeiten
	Aus rechentechnischen GrÃ¼nden wird oft als Induktionsschritt nicht von n auf n + 1 geschlossen sondern von n - 1 auf n
	macht aber ansonsten keinen Unterschied
	die manchmal die Umformungen vereinfacht
	Dies ist alledings lediglich eine NotationsÃ¤nderung
	auf denen eine partielle Ordnung definiert ist
	so zeigt sich
	Wenn man zu allgemeineren Mengen Ã¼bergehen will
	dass die vollstÃ¤ndige Induktion auf allen Mengen anwendbar ist
	wobei keine unendlichen absteigenden Ketten auftreten dÃ¼rfen (weil sonst keine Anfangselemente gefunden werden kÃ¶nnen)
	Eine solche Menge heiÃŸt fundierte Menge
	Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen kÃ¶nnen unendlich und grÃ¶ÃŸer werden)
	In diesem Fall wird die Methode transfinite Induktion genannt
	Sie ist wichtig in der Mengenlehre und der Topologie. bg:ÐœÐ°Ñ‚ÐµÐ¼Ð°Ñ‚Ð¸Ñ‡ÐµÑ?ÐºÐ° Ð¸Ð½Ð´ÑƒÐºÑ†Ð¸Ñ? en:Mathematical induction es:InducciÃ³n matemÃ¡tica he:×?×™× ×“×•×§×¦×™×” ×ž×ª×ž×˜×™×ª ja:æ•°å¦çš„å¸°ç´?æ³• it:Principio di induzione nl:Inductie (wiskunde) pl:Indukcja matematyczna pt:InduÃ§Ã£o matemÃ¡tica ru:ÐœÐ°Ñ‚ÐµÐ¼Ð°Ñ‚Ð¸Ñ‡ÐµÑ?ÐºÐ°Ñ? Ð¸Ð½Ð´ÑƒÐºÑ†Ð¸Ñ? sl:MatematiÄ?na indukcija tr:Matematiksel tÃ¼mevarÄ±m zh:æ•°å¦å½’çº³æ³•

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Induktion (Mathematik) aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.

II. Weltkrieg IP Internationalismus Internationalismus Internationaler Gerichtshof ICJ Sans papiers Jean-Jacques Annaud

[ Zurück ]

Inhalt Lexikon:

Allgemein

Definition

Motivation

Beispiel

Die Idee

Anderes Beispiel: Summe der ungeraden Zahlen

Bezeichnungen

Tipps zur Anwendung

Anwendungen

Verallgemeinerungen und Variationen

Beweis fÃ¼r fast alle natÃ¼rlichen Zahlen

Verwendung mehrerer VorgÃ¤nger

VorwÃ¤rts-rÃ¼ckwÃ¤rts-Induktion

Sonstige