[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki31\/2022\/01\/13\/vollstandige-induktion-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki31\/2022\/01\/13\/vollstandige-induktion-wikipedia\/","headline":"Vollst\u00e4ndige Induktion \u2013 Wikipedia","name":"Vollst\u00e4ndige Induktion \u2013 Wikipedia","description":"Die vollst\u00e4ndige Induktion ist eine mathematische Beweismethode, nach der eine Aussage f\u00fcr alle nat\u00fcrlichen Zahlen bewiesen wird, die gr\u00f6\u00dfer oder","datePublished":"2022-01-13","dateModified":"2022-01-13","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki31\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki31\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/2e9053cbbf69129ea1bcfdcd966618db3e190dfc","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/2e9053cbbf69129ea1bcfdcd966618db3e190dfc","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki31\/2022\/01\/13\/vollstandige-induktion-wikipedia\/","wordCount":30102,"articleBody":"Die vollst\u00e4ndige Induktion ist eine mathematische Beweismethode, nach der eine Aussage f\u00fcr alle nat\u00fcrlichen Zahlen bewiesen wird, die gr\u00f6\u00dfer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann eine Herleitung nicht f\u00fcr jede Zahl einzeln erbracht werden.  Der Beweis, dass die Aussage A\u2061(n){displaystyle operatorname {A} (n)} f\u00fcr alle n\u2265n0{displaystyle ngeq n_{0}} (  n0{displaystyle n_{0}} meist 1 oder 0) gilt,wird daher in zwei Etappen durchgef\u00fchrt:Im Induktionsanfang wird die Aussage A\u2061(n0){displaystyle operatorname {A} (n_{0})} f\u00fcr eine kleinste Zahl n0{displaystyle n_{0}}  hergeleitet.Im Induktionsschritt wird f\u00fcr ein beliebiges n\u2265n0{displaystyle ngeq n_{0}} die Aussage A\u2061(n+1){displaystyle operatorname {A} (n+1)} aus der Aussage A\u2061(n){displaystyle operatorname {A} (n)} hergeleitet.Oder weniger \u201emathematisch\u201c formuliert:Induktionsanfang: Es wird bewiesen, dass die Aussage f\u00fcr die kleinste Zahl, den Startwert, gilt.Induktionsschritt: Folgendes wird bewiesen: Gilt die Aussage f\u00fcr eine beliebige Zahl, so gilt sie auch f\u00fcr die Zahl eins gr\u00f6\u00dfer.Ausgehend vom Beweis f\u00fcr den Startwert erledigt der Induktionsschritt den Beweis f\u00fcr alle nat\u00fcrlichen Zahlen oberhalb des Startwertes.Dieses Beweisverfahren ist von grundlegender Bedeutung f\u00fcr die Arithmetik und Mengenlehre und damit f\u00fcr alle Gebiete der Mathematik.  Die vollst\u00e4ndige Induktion befasst sich mit der G\u00fcltigkeit von Aussageformen A\u2061(n){displaystyle operatorname {A} (n)}.Beispiel (Siehe Gau\u00dfsche Summenformel):A\u2061(n):1+2+3+\u22ef+n=n\u22c5(n+1)2{displaystyle operatorname {A} (n):1+2+3+dots +n={tfrac {ncdot (n+1)}{2}}} f\u00fcr n\u22651{displaystyle ngeq 1}Wenn man Werte f\u00fcr n\u2208N{displaystyle nin mathbb {N} } einsetzt, erh\u00e4lt man Aussagen, die wahr oder falsch sind.A\u2061(1):1=1\u22c5(1+1)2{displaystyle operatorname {A} (1):1={tfrac {1cdot (1+1)}{2}}}A\u2061(2):1+2=2\u22c5(2+1)2{displaystyle operatorname {A} (2):1+2={tfrac {2cdot (2+1)}{2}}}A\u2061(3):1+2+3=3\u22c5(3+1)2{displaystyle operatorname {A} (3):1+2+3={tfrac {3cdot (3+1)}{2}}}\u22ee{displaystyle vdots }Die Aussagen im obigen Beispiel sind offensichtlich alle wahr. Da man das nicht f\u00fcr alle (unendlich viele) Zahlen nachrechnen kann, bedarf es eines besonderen Beweisverfahrens. Dieses liefert die vollst\u00e4ndige Induktion.Die Aussageform A\u2061(n){displaystyle operatorname {A} (n)} ist allgemeing\u00fcltig, wenn sie f\u00fcr alle n\u2208N{displaystyle nin mathbb {N} } wahr ist.Um die Allgemeing\u00fcltigkeit der Aussageform A\u2061(n){displaystyle operatorname {A} (n)} zu beweisen, zeigt man Folgendes:A\u2061(1){displaystyle operatorname {A} (1)} (Induktionsanfang) undaus der Aussage (der Induktionsannahme) A\u2061(n){displaystyle operatorname {A} (n)} folgt stets die Aussage A\u2061(n+1){displaystyle operatorname {A} (n+1)}, und zwar f\u00fcr alle n\u2208N{displaystyle nin mathbb {N} }. (Das ist der Induktionsschritt.)[1]  Vollst\u00e4ndige Induktion als Dominoeffekt mit unendlich vielen SteinenDie Methode der vollst\u00e4ndigen Induktion ist mit dem Dominoeffekt vergleichbar: Wenn der erste Dominostein f\u00e4llt und durch jeden fallenden Dominostein der n\u00e4chste umgesto\u00dfen wird, wird schlie\u00dflich jeder Dominostein der unendlich lang gedachten Kette irgendwann umfallen.Die Allgemeing\u00fcltigkeit einer Aussageform A\u2061(n){displaystyle operatorname {A} (n)} ist f\u00fcr n=1,2,3,\u2026{displaystyle n=1,2,3,ldots } bewiesen, wenn A\u2061(1){displaystyle operatorname {A} (1)} g\u00fcltig ist (der erste Stein f\u00e4llt um) und wenn zus\u00e4tzlich gilt A\u2061(n)\u21d2A\u2061(n+1){displaystyle operatorname {A} (n)Rightarrow operatorname {A} (n+1)} f\u00fcr n=1,2,3,\u2026{displaystyle n=1,2,3,ldots } (jeder Stein rei\u00dft beim Umfallen den n\u00e4chsten Stein mit).Die Bezeichnung Induktion leitet sich ab von lat. inductio, w\u00f6rtlich \u201eHineinf\u00fchrung\u201c. Der Zusatz vollst\u00e4ndig signalisiert, dass es sich hier im Gegensatz zur philosophischen Induktion, die aus Spezialf\u00e4llen ein allgemeines Gesetz erschlie\u00dft und kein exaktes Schlussverfahren ist, um ein anerkanntes deduktives Beweisverfahren handelt.Das Induktionsprinzip steckt latent bereits in der von Euklid \u00fcberlieferten pythagoreischen Zahlendefinition: \u201eZahl ist die aus Einheiten zusammengesetzte Menge.\u201c[2] Euklid f\u00fchrte aber noch keine Induktionsbeweise, sondern begn\u00fcgte sich mit intuitiven, exemplarischen Induktionen, die sich aber vervollst\u00e4ndigen lassen. Auch andere bedeutende Mathematiker der Antike und des Mittelalters hatten noch kein Bed\u00fcrfnis nach pr\u00e4zisen Induktionsbeweisen. Vereinzelte Ausnahmen im hebr\u00e4ischen und arabischen Sprachraum blieben ohne Nachfolge.[3][4]Lange galt ein Beweis von Franciscus Maurolicus von 1575 als \u00e4lteste explizite vollst\u00e4ndige Induktion (unten ausgef\u00fchrt).[5] Er er\u00f6rterte aber das allgemeine Beweisverfahren noch nicht. Erst Blaise Pascal thematisierte das Induktionsprinzip mit Induktionsanfang und Induktionsschritt in seinem Trait\u00e9 du triangle arithm\u00e9tique von 1654.[6] Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob I Bernoulli wesentlich bei.[7]Das Beweisverfahren wurde dann 1838 von Augustus De Morgan erstmals als Induktion oder sukzessive Induktion bezeichnet.[8] 1888 pr\u00e4gte schlie\u00dflich Richard Dedekind in seiner Schrift Was sind und was sollen die Zahlen? den Begriff vollst\u00e4ndige Induktion.[9] \u00dcber dieses Werk aus der Gr\u00fcnderzeit der Mengenlehre wurde sie zum allgemein bekannten, etablierten Beweisprinzip, auf das seither kein Zweig der Mathematik mehr verzichten kann. Ein Jahr sp\u00e4ter, 1889, formulierte Giuseppe Peano mit den Peanoschen Axiomen den ersten formalisierten Kalk\u00fcl f\u00fcr die nat\u00fcrlichen Zahlen mit einem Induktionsaxiom, aus dem das Beweisschema der vollst\u00e4ndigen Induktion herleitbar ist.[10] Er zeigte mit formaler Strenge, dass aus seinen Zahlaxiomen, zu denen das Induktionsaxiom geh\u00f6rt, die ganze Arithmetik bis hin zu den reellen Zahlen ableitbar ist. Dadurch machte er die fundamentale Bedeutung und die Leistungskraft der Induktion voll bewusst.Seit Richard Dedekind ist die vollst\u00e4ndige Induktion folgenderma\u00dfen festgelegt:Um zu beweisen, dass ein Satz f\u00fcr alle nat\u00fcrlichen Zahlen n\u2265n0{displaystyle ngeq n_{0}} gilt, gen\u00fcgt es zu zeigen,dass er f\u00fcr n=n0{displaystyle n=n_{0}} gilt unddass aus der G\u00fcltigkeit des Satzes f\u00fcr eine Zahl n\u2265n0{displaystyle ngeq n_{0}} stets seine G\u00fcltigkeit auch f\u00fcr die folgende Zahl n+1{displaystyle n+1} folgt.[9]Als formale Schlussregel mit Ableitungsoperator \u22a2{displaystyle vdash } lautet die vollst\u00e4ndige Induktion f\u00fcr eine Aussage A\u2061(n){displaystyle operatorname {A} (n)} und eine nat\u00fcrliche Zahl n0{displaystyle n_{0}}:A\u2061(n0){displaystyle operatorname {A} (n_{0})} und \u2200n\u2208N:(n\u2265n0\u2227A\u2061(n)\u21d2A\u2061(n+1))\u00a0\u22a2\u00a0\u2200n\u2208N:(n\u2265n0\u21d2A\u2061(n)){displaystyle forall nin mathbb {N} colon (ngeq n_{0}land operatorname {A} (n)Rightarrow operatorname {A} (n+1)) vdash  forall nin mathbb {N} colon (ngeq n_{0}Rightarrow operatorname {A} (n))}Diese Schlussregel ist eine kompakte Formulierung des Beweisschemas der vollst\u00e4ndigen Induktion, das didaktisch etwas ausf\u00fchrlicher formuliert werden kann:Soll die Formel A\u2061(n){displaystyle operatorname {A} (n)} f\u00fcr alle nat\u00fcrlichen Zahlen n\u2265n0{displaystyle ngeq n_{0}} bewiesen werden, dann gen\u00fcgen dazu zwei schritte:der Induktionsanfang: der  von A\u2061(n0){displaystyle operatorname {A} (n_{0})},der Induktionsschritt (auch \u00bbSchluss von n{displaystyle n} auf n+1{displaystyle n+1}\u00ab[9] genannt): der  der Induktionsbehauptung A\u2061(n+1){displaystyle operatorname {A} (n+1)} aus n\u2265n0{displaystyle ngeq n_{0}} und der Induktionsvoraussetzung (auch Induktionsannahme, engl. induction hypothesis) A\u2061(n){displaystyle operatorname {A} (n)}.Nach obiger Schlussregel folgt dann die Verallgemeinerung der Formel A\u2061(n){displaystyle operatorname {A} (n)} auf alle nat\u00fcrlichen Zahlen n\u2265n0{displaystyle ngeq n_{0}} (der abschlie\u00dfende Induktionsschluss).Die f\u00fcr nat\u00fcrliche Zahlen k\u2208K{displaystyle kin K} aus einer Menge K\u2286N{displaystyle Ksubseteq mathbb {N} } zu beweisende Aussage A\u2061(k){displaystyle operatorname {A} (k)} tritt hierbei in mindestens 3 Rollen auf:(1)als Induktionsbehauptungf\u00fcr ein (einzelnes) beliebiges n\u2208K{displaystyle nin K}(2)als Induktionsvoraussetzungf\u00fcr endlich viele kleinere nat\u00fcrliche Zahlen k\u2208K{displaystyle kin K}(3)als zu beweisende allgemeine Aussagef\u00fcr alle (und damit f\u00fcr unendlich viele) n\u2208K{displaystyle nin K}Meist ist n0=0{displaystyle n_{0}=0} oder n0=1{displaystyle n_{0}=1}. 1}”\/> ist jedoch m\u00f6glich.Denn da die Aussage A\u2061(n){displaystyle operatorname {A} (n)} f\u00fcr n\u2265n0{displaystyle ngeq n_{0}} gleichwertig ist zur Aussage B(n):=A(n+n0){displaystyle B(n):=A(n+n_{0})} f\u00fcr n\u22650{displaystyle ngeq 0}, l\u00e4sst sich Dedekinds Induktion auf die vollst\u00e4ndige Induktion von 0 aus zur\u00fcckf\u00fchren:B\u2061(0),\u2200n\u2208N:(B\u2061(n)\u21d2B\u2061(n+1))\u00a0\u22a2\u00a0\u2200n\u2208N:B\u2061(n)\u21d1\u21d1\u21d3A\u2061(0+n0),\u2200n\u2208N:(A\u2061(n+n0)\u21d2A\u2061(n+1+n0))\u00a0A\u2061(n+n0){displaystyle {begin{array}{llll}operatorname {B} (0){,}&&&forall nin mathbb {N} colon (operatorname {B} (n)&Rightarrow operatorname {B} (n+1)) &&&vdash  forall nin mathbb {N} colon &operatorname {B} (n)\\Uparrow &&&&Uparrow &&&&Downarrow \\operatorname {A} (0+n_{0}){,}&&&forall nin mathbb {N} colon (operatorname {A} (n+n_{0})&Rightarrow operatorname {A} (n+1+n_{0})) &&&&operatorname {A} (n+n_{0})end{array}}}Peano bewies 1889 mit vollst\u00e4ndiger Induktion die grundlegenden Rechenregeln f\u00fcr die Addition und Multiplikation: das Assoziativgesetz, Kommutativgesetz und Distributivgesetz.[11][12]Die vollst\u00e4ndige Induktion ist ein Axiom der nat\u00fcrlichen Zahlen. Meist wird sie jedoch aus dem gleichwertigen f\u00fcnften Peano-Axiom, dem Induktionsaxiom, hergeleitet. Dieses lautet:Ist K{displaystyle ,K} eine Teilmenge der nat\u00fcrlichen Zahlen N{displaystyle mathbb {N} } mit den Eigenschaften:1{displaystyle ,1} ist ein Element von K{displaystyle ,K}Mit n{displaystyle ,n} aus K{displaystyle ,K} ist stets auch n+1{displaystyle ,n+1} aus K{displaystyle ,K},dann ist K=N{displaystyle ,K=mathbb {N} }.Auch in anderen Konzepten der nat\u00fcrlichen Zahlen sind die Peano-Axiome und damit auch das Beweisverfahren der vollst\u00e4ndigen Induktion herleitbar, zum Beispiel bei der Definition der nat\u00fcrlichen Zahlenals von 1 erzeugte geordnete Halbgruppe, die der zitierten pythagoreischen Zahlendefinition entspricht[2]als frei von 1 erzeugtes Monoid, das von der Addition der Zahlen ausgeht[13]als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht[14][15]als kleinste induktive Menge, n\u00e4mlich als kleinste Menge, die das Unendlichkeitsaxiom erf\u00fcllt, wie es in der Mengenlehre \u00fcblich istals Klasse der endlichen Ordinalzahlen, die nur eine allgemeine Mengenlehre ohne Unendlichkeitsaxiom voraussetztTable of ContentsGau\u00dfsche Summenformel[Bearbeiten | Quelltext bearbeiten]Summe ungerader Zahlen (Maurolicus 1575)[Bearbeiten | Quelltext bearbeiten]Bernoullische Ungleichung[Bearbeiten | Quelltext bearbeiten]Pferde-Paradox[Bearbeiten | Quelltext bearbeiten]Induktion mit beliebigem Anfang[Bearbeiten | Quelltext bearbeiten]Starke Induktion[Bearbeiten | Quelltext bearbeiten]Induktion mit mehreren Vorg\u00e4ngern[Bearbeiten | Quelltext bearbeiten]Formale Definition[Bearbeiten | Quelltext bearbeiten]Induktion mit Vorw\u00e4rts-R\u00fcckw\u00e4rts-Schritten[Bearbeiten | Quelltext bearbeiten]Weitere Induktionsvarianten[Bearbeiten | Quelltext bearbeiten]Gau\u00dfsche Summenformel[Bearbeiten | Quelltext bearbeiten]Die Gau\u00dfsche Summenformel lautet:\u00a0 \u00a0 F\u00fcr alle nat\u00fcrlichen Zahlen n\u22651{displaystyle ngeq 1} gilt die Aussage\u00a0 \u00a0 A\u2061(n):\u27fa{displaystyle operatorname {A} (n):Longleftrightarrow }1+2+\u22ef+n{displaystyle 1+2+cdots +n}=n(n+1)2{displaystyle ={frac {n(n+1)}{2}}}.Sie kann durch vollst\u00e4ndige Induktion bewiesen werden.Der Induktionsanfang ergibt sich unmittelbar:\u00a0 \u00a0 A\u2061(1)\u27fa{displaystyle operatorname {A} (1)Longleftrightarrow }1{displaystyle 1}=1(1+1)2{displaystyle ={frac {1(1+1)}{2}}}.Im Induktionsschritt ist zu zeigen, dass f\u00fcr n\u22651{displaystyle ngeq 1} aus der Induktionsvoraussetzung\u00a0 \u00a0 A\u2061(n)\u27fa{displaystyle operatorname {A} (n)Longleftrightarrow }1+2+\u22ef+n{displaystyle 1+2+cdots +n}=n(n+1)2{displaystyle ={frac {n(n+1)}{2}}}die Induktionsbehauptung\u00a0 \u00a0 A\u2061(n+1)\u27fa{displaystyle operatorname {A} (n!+!1)Longleftrightarrow }1+2+\u22ef+(n+1){displaystyle 1+2+cdots +(n!+!1)}=(n+1)((n+1)+1)2{displaystyle ={frac {(n!+!1){bigl (}(n!+!1)+1{bigr )}}{2}}}=(n+1)(n+2)2{displaystyle ={frac {(n+1)(n+2)}{2}}}(mit (n+1){displaystyle (n!+!1)} an der Stelle des n{displaystyle n} der Induktionsvoraussetzung) folgt.Dies gelingt folgenderma\u00dfen:Abschlie\u00dfend der Induktionsschluss:\u00a0 \u00a0 Damit ist die Aussage A\u2061(n){displaystyle operatorname {A} (n)} f\u00fcr alle n\u22651{displaystyle ngeq 1} bewiesen.Summe ungerader Zahlen (Maurolicus 1575)[Bearbeiten | Quelltext bearbeiten]Beweis der Summenformel \u00fcber ungerade Zahlen mit Hilfe der vollst\u00e4ndigen InduktionDie schrittweise Berechnung der Summe der ersten n{displaystyle n} ungeraden Zahlen legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von 1{displaystyle 1} bis 2n\u22121{displaystyle 2n-1} ist gleich dem Quadrat von n{displaystyle n}:1=1{displaystyle 1=1}1+3=4{displaystyle 1+3=4}1+3+5=9{displaystyle 1+3+5=9}1+3+5+7=16{displaystyle 1+3+5+7=16}Der zu beweisende allgemeine Satz lautet: \u2211i=1n(2i\u22121)=n2{displaystyle textstyle sum limits _{i=1}^{n}(2i-1)=n^{2}}. Ihn bewies Maurolicus 1575 mit vollst\u00e4ndiger Induktion.[5] Ein Beweis mit heute gel\u00e4ufigen Rechenregeln liest sich folgenderma\u00dfen:Der Induktionsanfang \u2211i=11(2i\u22121)=12{displaystyle textstyle sum limits _{i=1}^{1}(2i-1)=1^{2}} mit n=1{displaystyle n=1} ist wegen \u2211i=11(2i\u22121)=2\u22c51\u22121=1=12{displaystyle textstyle sum limits _{i=1}^{1}(2i-1)=2cdot 1-1=1=1^{2}} leicht nachgepr\u00fcft.Als Induktionsschritt ist zu zeigen: Wenn \u2211i=1n(2i\u22121)=n2{displaystyle textstyle sum limits _{i=1}^{n}(2i-1)=n^{2}}, dann \u2211i=1n+1(2i\u22121)=(n+1)2{displaystyle textstyle sum limits _{i=1}^{n+1}(2i-1)=(n+1)^{2}}. Er ergibt sich \u00fcber folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:\u2211i=1n+1(2i\u22121)=\u2211i=1n(2i\u22121)+(2(n+1)\u22121)\u00a0=\u00a0n2+2(n+1)\u22121=n2+2n+1=(n+1)2{displaystyle {begin{aligned}sum _{i=1}^{n+1}(2i-1);&=;;{color {red}sum _{i=1}^{n}(2i-1)}+(2(n+1)-1)\\& {color {red}=;; n^{2}}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}end{aligned}}}(Die Induktionsvoraussetzung ist rot markiert.)Bernoullische Ungleichung[Bearbeiten | Quelltext bearbeiten]Die Bernoullische Ungleichung lautet f\u00fcr reelle Zahlen x{displaystyle ,x} mit x\u2265\u22121{displaystyle xgeq -1} und nat\u00fcrliche Zahlenn\u22650{displaystyle ngeq 0}(1+x)n\u22651+nx{displaystyle (1+x)^{n}geq 1+nx}.Der Induktionsanfang mit n=0{displaystyle n=0} gilt hier wegen (1+x)0=1\u22651{displaystyle (1+x)^{0}=1geq 1} (wobei die Definitionsl\u00fccke an der Stelle x=\u22121{displaystyle x=-1} durch limx\u2198\u22121(1+x)0=1{displaystyle lim _{xsearrow -1}(1+x)^{0}=1} stetig erg\u00e4nzt ist).Den Induktionsschritt gewinnt man \u00fcber folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei obige Bedingung f\u00fcr x{displaystyle ,x} daf\u00fcr sorgt, dass der Term nicht negativ wird:(1+x)n+1=(1+x)n\u22c5(1+x)\u2265(1+nx)\u22c5(1+x)=1+x+nx+nx2\u22651+x+nx=1+(n+1)x.{displaystyle {begin{aligned}(1+x)^{n+1}&={color {red}(1+x)^{n}}cdot (1+x),,{color {red}geq ;(1+nx)}cdot (1+x)\\&=1+x+nx+nx^{2};geq ;1+x+nx\\&=1+(n+1)x.end{aligned}}}(Die Induktionsvoraussetzung ist rot markiert.)Das zweimalige Vorkommen des \u2265{displaystyle geq }-Zeichens (in gleicher Richtung) l\u00e4sst sich vereinfachen zu:(1+x)n+1\u22651+(n+1)x.{displaystyle (1+x)^{n+1}geq 1+(n+1)x.}Pferde-Paradox[Bearbeiten | Quelltext bearbeiten]Das Pferde-Paradox ist ein Standardbeispiel f\u00fcr eine fehlerhafte Anwendung der vollst\u00e4ndigen Induktion und illustriert die Bedeutung des Zusammenspiels von Induktionsverankerung und Induktionsschritt. Bei ihm wird die unsinnige Aussage, dass in einer Herde von n{displaystyle n} Pferden alle immer die gleiche Farbe besitzen, anhand einer scheinbar korrekten Induktion bewiesen. Dabei ist der Induktionsschritt selbst korrekt, w\u00fcrde aber die Induktionsverankerung bei einem n\u22652{displaystyle ngeq 2} ben\u00f6tigen, w\u00e4hrend der (fehlerhafte) Beweis die Induktion bei n=1{displaystyle n=1} verankert und somit schon der Schritt von n=1{displaystyle n=1} auf n=2{displaystyle n=2} scheitert.Induktion mit beliebigem Anfang[Bearbeiten | Quelltext bearbeiten]Induktionsbeweis der Ungleichung 2n\u2265n2{displaystyle 2^{n}geq n^{2}} f\u00fcr nat\u00fcrliche Zahlen n\u22654{displaystyle ngeq 4}:Der Induktionsanfang f\u00fcr n=4{displaystyle ,n=4} ergibt sich mit 24=16\u226516=42{displaystyle 2^{4}=16geq 16=4^{2}}.Der Induktionsschritt gilt aufgrund folgender Ableitung, die im zweiten Schritt die Induktionsvoraussetzung und im vierten und sechsten Schritt die Voraussetzung n\u22654{displaystyle ngeq 4} anwendet:2n+1=2\u22c52n\u22652\u22c5n2=n2+n\u22c5n\u2265n2+4n=n2+2n+2n\u2265n2+2n+2\u22c54\u2265n2+2n+1=(n+1)2.{displaystyle {begin{array}{lll}2^{n+1}&=2cdot 2^{n}geq 2cdot n^{2}&=n^{2}+ncdot ngeq n^{2}+4n\\&=n^{2}+2n+2n&geq n^{2}+2n+2cdot 4\\&geq n^{2}+2n+1&=(n+1)^{2}.end{array}}}Die endlich vielen F\u00e4lle, die solch ein allgemeinerer Induktionsbeweis nicht abdeckt, k\u00f6nnen einzeln untersucht werden. Im Beispiel ist die Ungleichung f\u00fcr n=3{displaystyle n=3} offenbar falsch.Starke Induktion[Bearbeiten | Quelltext bearbeiten]Induktion mit mehreren Vorg\u00e4ngern[Bearbeiten | Quelltext bearbeiten]In manchen Induktionsbeweisen kommt man in der Induktionsvoraussetzung mit dem Bezug auf einen einzigen Vorg\u00e4nger nicht aus, bspw. wenn eine Rekursionsformel mehrere Vorg\u00e4nger enth\u00e4lt.[16]Der Induktionsanfang ist dann f\u00fcr mehrere Startwerte durchzuf\u00fchren.Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung f\u00fcr n{displaystyle n} und n\u22121{displaystyle n-1} n\u00f6tig, dann ist ein Induktionsanfang f\u00fcr zwei aufeinander folgende Zahlen, also etwa 0 und 1, erforderlich. Als Induktionsvoraussetzung kann auch die Aussage f\u00fcr alle Zahlen zwischen dem Startwert und n{displaystyle n} dienen. Ein Beispiel[17] ist der Beweis, dass jede nat\u00fcrliche Zahl n\u22652{displaystyle ngeq 2} einen Primzahl-Teiler hat:Induktionsanfang: 2 ist durch die Primzahl 2 teilbar.Induktionsschritt: Die Aussage sei f\u00fcr alle m{displaystyle m} mit 2\u2264m\u2264n{displaystyle 2leq mleq n} erf\u00fcllt. Ist nun n+1{displaystyle n+1} eine Primzahl, so ist n+1{displaystyle n+1} selbst der gesuchte Teiler, und die Behauptung ist bewiesen. Ist n+1{displaystyle ,n+1} keine Primzahl, so gibt es zwei Zahlen a,b\u2208N{displaystyle a,bin mathbb {N} } mit a\u22c5b=n+1{displaystyle acdot b=n+1} und 1n0{displaystyle ngeq n_{0}} g\u00fcltig, wenn Folgendes f\u00fcr jedes beliebige n\u2265n0{displaystyle ngeq n_{0}} gezeigt wird:(Induktionsschritt:)\u22c0m=n0n\u22121A\u2061(m)\u27f9A\u2061(n){displaystyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)implies operatorname {A} (n)} .Das Beweisschema der starken Induktion besteht demgem\u00e4\u00df nur aus dem Induktionsschritt.Induktionsanf\u00e4nge, wie sie in der gew\u00f6hnlichen Induktion vorkommen, also bspw. der Nachweis der Aussage A\u2061(n0){displaystyle operatorname {A} (n_{0})}, sind im Induktionsschritt enthalten.[19] Es kann \u00fcberdies vorkommen, dass mehr als eine Anfangsaussage vorab zu zeigen ist (siehe Fibonacci-Folge).Offensichtlich folgt die (in der Einleitung formulierte) gew\u00f6hnliche vollst\u00e4ndige Induktion aus der starken Induktion. Man kann aber auch die starke Induktion mit Hilfe der gew\u00f6hnlichen vollst\u00e4ndigen Induktion beweisen.[20]Beweis\u00a0\u00a0Zu zeigen ist:Wenn f\u00fcr alle n\u2265n0{displaystyle ngeq n_{0}}aus \u22c0m=n0n\u22121A\u2061(m){displaystyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}}{displaystyle left.{begin{matrix}\\\\\\\\end{matrix}}rightrbrace }(Induktionsvoraussetzung gew\u00f6hnlich \u21d2 stark)A\u2061(n){displaystyle operatorname {A} (n)} folgt,dann giltA\u2061(n){displaystyle operatorname {A} (n)} f\u00fcr  n\u2265n0{displaystyle ngeq n_{0}}.(Induktionsschluss gew\u00f6hnlich \u21d2 stark)Wir definieren die folgende Aussage B{displaystyle operatorname {B} } f\u00fcr nat\u00fcrliche Zahlen n\u2208N,n\u2265n0{displaystyle nin mathbb {N} ,ngeq n_{0}}B\u2061(n):\u27fa\u22c0m=n0n\u22121A\u2061(m){displaystyle operatorname {B} (n):Longleftrightarrow bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}und zeigen ihre G\u00fcltigkeit mittels gew\u00f6hnlicher vollst\u00e4ndiger Induktion.Induktionsanfang: Da B\u2061(n0)\u27fa\u22c0m=n0n0\u22121A\u2061(m)\u27fa\u22c0m\u2208\u2205A\u2061(m){displaystyle operatorname {B} (n_{0})Longleftrightarrow textstyle bigwedge _{m=n_{0}}^{n_{0}-1}operatorname {A} (m)Longleftrightarrow bigwedge _{min emptyset }operatorname {A} (m)}, die leere Und-Verkn\u00fcpfung ist, gilt B\u2061(n0){displaystyle operatorname {B} (n_{0})} gem\u00e4\u00df Anmerkung[19] sofort.(Gew\u00f6hnlicher) Induktionsschritt von n{displaystyle n} nach n+1{displaystyle n+1}:Sei n\u2265n0{displaystyle ngeq n_{0}} beliebig und es gelte B\u2061(n){displaystyle operatorname {B} (n)}, d.\u00a0h. es gelte\u22c0m=n0n\u22121A\u2061(m){displaystyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)}.Wegen der (Induktionsvoraussetzung gew\u00f6hnlich \u21d2 stark) folgt darausA\u2061(n){displaystyle operatorname {A} (n)}.Zusammengenommen mit \u22c0m=n0n\u22121A\u2061(m){displaystyle textstyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)} ergibt dies\u22c0m=n0nA\u2061(m){displaystyle bigwedge _{m=n_{0}}^{n}operatorname {A} (m)}.Damit haben wir B\u2061(n+1){displaystyle operatorname {B} (n+1)} gezeigt, welches \u27fa\u22c0m=n0nA\u2061(m){displaystyle Longleftrightarrow textstyle bigwedge _{m=n_{0}}^{n}operatorname {A} (m)} ist, und der gew\u00f6hnliche Induktionsschritt ist fertig. Wir schlie\u00dfen (gew\u00f6hnlicher Induktionsschluss):F\u00fcr  n\u2208N,n\u2265n0{displaystyle nin mathbb {N} ,ngeq n_{0}} gilt B\u2061(n){displaystyle operatorname {B} (n)}.Wegen B\u2061(n)\u27fa\u22c0m=n0n\u22121A\u2061(m){displaystyle operatorname {B} (n)Longleftrightarrow textstyle bigwedge _{m=n_{0}}^{n-1}operatorname {A} (m)} ergibt sich a fortiori der starke Induktionsschluss:F\u00fcr  n\u2208N,n\u2265n0{displaystyle nin mathbb {N} ,ngeq n_{0}} gilt A\u2061(n){displaystyle operatorname {A} (n)}.\u00a0\u00a0\u25a0Trotz dieser prinzipiellen Gleichwertigkeit in der Beweisst\u00e4rke ist der Unterschied in der Ausdrucksst\u00e4rke wegen der beliebig vielen Startwerte und der M\u00f6glichkeit des R\u00fcckgriffs auf beliebig viele Vorg\u00e4nger gro\u00df, besonders bei rekursiven Definitionen. Das bedeutet aber keineswegs, dass letztere Definitionen nicht in gew\u00f6hnliche Rekursionen \u00fcberf\u00fchrt werden k\u00f6nnen.BeispielInduktion mit Vorw\u00e4rts-R\u00fcckw\u00e4rts-Schritten[Bearbeiten | Quelltext bearbeiten]Augustin-Louis Cauchy f\u00fchrte 1821 eine Induktionsvariante vor, bei der der vorw\u00e4rts gerichtete Induktionsschritt Spr\u00fcnge macht (n\u00e4mlich von 2k{displaystyle 2^{k}} nach 2k+1{displaystyle 2^{k+1}}) und die entstandenen L\u00fccken nachtr\u00e4glich durch eine r\u00fcckw\u00e4rts gerichtete Herleitung von 2k{displaystyle 2^{k}} nach nr\u00a0n=1n+f(n\u22121)fu\u00a8r\u00a0n>1{displaystyle f(n)={begin{cases}1&&mathrm {f{ddot {u}}r}  n=1\\n+f(n-1)&&mathrm {f{ddot {u}}r}  n>1\\end{cases}}}"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki31\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki31\/2022\/01\/13\/vollstandige-induktion-wikipedia\/#breadcrumbitem","name":"Vollst\u00e4ndige Induktion \u2013 Wikipedia"}}]}]