Mathematik: Analysis I - §2 Die Beweisverfahren
Released by matroid on Fr. 04. April 2008 16:22:18 [Statistics]
Written by da_bounce - 19844 x read [Outline] Printable version Printer-friendly version -  Choose language   
Analysis

\(\begingroup\)\(- Student der Mathematik bis zum 5. Semester - Studium der Luft- und Raumfahrttechnik mit Schwerpunkt Luftverkehr - Quereinstieg in die Informationssicherheit - tätig als Consultant für Cyber Defense\) da_bounce und FlorianM schreiben:

§2 Die Beweisverfahren

Im ersten Teil unserer Vorlesung über die Analysis I haben wir schon einige Sätze und Behauptungen bewiesen. Nun wollen wir nacheinander verschiedene Beweismethoden der Mathematik motivieren und einführen, damit wir ab Kapitel 3 diese dann im Schlaf beherrschen. Vor allem die vollständige Induktion muss euch in Fleisch und Blut übergehen. Deshalb wird es dazu auch die meisten Beispiele geben. Es gab schon früher einen Artikel über "Die Beweisverfahren". Wenn man diesen auch noch liest und sich weitere Beispiele im Internet oder in Büchern anschaut, sollte man nach und nach das Beweisen lernen. Wir geben aber auch zu, dass man bei einigen Behauptungen schon eine sehr pfiffige Idee braucht, und es für Anfänger fast unmöglich ist, ohne Hilfe auf diese Idee zu kommen. Aber nur durch kontinuierliches Üben kann man die Beweismethoden trainieren.


§2 Die Beweisverfahren

\grey\ \big\ Inhalt dieses Artikels: \darkblue\ \big\ 2. Die Beweisverfahren 2.1 Direkter Beweis 2.2 Indirekter Beweis 2.3 Konstruktive Beweise 2.4 Vollständige Induktion 2.5 Lösungen zu den Übungsaufgaben In euer ersten Vorlesungswoche werdet ihr schnell feststellen, dass ihr eine komplett andere Mathematik lernen werdet. Diese besteht aus Definitionen, Sätzen und Beweisen. Es braucht eine gewisse Zeit bis ihr euch an das, was man als Universitätsmathematik bezeichnet, gewöhnt habt. Wer Mathematik studiert, muss sich an den Stil der Vorlesung erstmal gewöhnen. Das Tempo in der Universität ist schnell, wenn nicht sogar rasend schnell und einige werden damit zu kämpfen haben. Ja, auch uns ging das teilweise so. Wie hat man sich das vorzustellen? Wenn man zuvor noch keine Uni geschnuppert hat, der wird sicher denken, dass man sich in eine Vorlesung reinsetzen wird und nach Ablauf der Zeit hat man das verstanden, was dort erzählt wurde. Sprich wie der Mathematikunterricht in der Schule. Der Lehrer erzählt was, gibt dann Beispiele zu dem Thema und danach darf der Schüler alleine rechnen. Wir wollen euch nicht gleich entmutigen, aber vergesst einfach die Art und Weise wie "Mathematik" in der Schule euch beigebracht wurde. Nun wollt ihr an die Universität oder seid es bereits. Dort werdet ihr was anderes zu Gesicht bekommen. An der Uni steht der Dozent an einer großen Tafel und schreibt meistens irgendwelche Definitionen, Sätze, Theoreme an. Ab und an werden dann noch diese Sätze oder Definitionen bewiesen. Es gibt aber auch Dozenten, die es sich ein wenig einfacher machen und dann Dinge sagen wie z.B. "Der Satz ist trivial und muss nicht bewiesen werden"; "Na, das folgt doch gerade aus dem Satz, den ich an die Tafel geschrieben habe" oder er sagt zu seinen Studenten: "Den Satz könnt ihr ganz leicht in der S-Bahn beweisen." Es könnte also gut sein, dass damalige Überflieger, also damit meinen wir Schüler, die in Mathe immer durchweg 12-15 Punkte hatten, schnell an ihre Grenzen stoßen und das erste Mal wahrscheinlich dazu gezwungen werden, sich ausgiebig mit der Mathematik an der Universität zu beschäftigen. Nach diesem weiteren kurzen Vorwort wollen wir nun endlich mit Kapitel 2 starten.
Die übliche Vorgehensweise in der Mathematik und auch in der Vorlesung ist, dass man zuerst eine Definition angibt, danach einen Satz, diesen Satz dann beweist und eventuell noch einige Anwendungen aufzeigt. Und mit Hilfe von verschiedenen Beweismethoden können diese Sätze und Aussagen bewiesen werden. \ \big In der Mathematik gibt es drei grundlegende Beweisprinzipien, mit denen man versucht, die Gültigkeit von bestimmten mathematischen Aussagen zu beweisen. 2.1 Direkter Beweis Man geht von der (gegebenen, wahren) Voraussetzung A aus und zeigt durch Umformen oder Folgern, dass aus A die Aussage B folgt. Mathematisch ausgedrückt untersucht man: \ \big \red A => B Starten wir mit einem Beispiel: \ Bekanntlich gilt der folgende \big\Satz__: Die Summe zweier gerader ganzer Zahlen ist gerade. Aber wie beweist man sowas? Wie wird solch ein Beweis geführt? Wir nehmen uns einfach zwei gerade ganze Zahlen, aber machen das allgemein. Genauer: Für beliebige gerade ganze Zahlen. \big\Beweis__: Seien x und y gerade ganze Zahlen (unsere Voraussetzung). Weil x gerade sein soll wissen wir, dass x durch 2 teilbar ist, d.h 2 teilt x oder anders geschrieben 2\|x. Dasselbe machen wir mit y, weil y gerade ist, wissen wir, dass y durch 2 teilbar ist, d.h 2 teilt y oder 2\|y. Weil 2\|x gilt, gibt es eine ganze Zahl a, so dass x=2a ist. Weiterhin gibt es wegen 2\|y eine ganze Zahl b, so dass y=2b ist. \stress Um uns das zu verdeutlichen, nehmen wir uns zwei ganz bestimmte gerade Zahlen x und y: \darkblue\ Sei x=4 und y=6 gerade ganze Zahlen (unsere Voraussetzung) \darkblue\ Weil x=4 ist wissen wir, dass 4 durch 2 teilbar ist, \darkblue\ d.h. 2 teilt 4 oder 2\|4. \darkblue\ Weil y=6 ist wissen wir, dass 6 durch 2 teilbar ist, \darkblue\ d.h. 2 teilt 6 oder 2\|6. \darkblue\ Weil 2\|4 gilt, gibt es eine weitere ganze Zahl a so dass 4=2a ist. \darkblue\ (hier a=2) \darkblue\ Weil 2\|6 gilt, gibt es eine weitere ganze Zahl b so dass 6=2b ist. \darkblue\ (hier b=3) Nun führen wir unseren Beweis fort: Durch Einsetzen und Ausklammern erhalten wir: x+y=2a+2b=2(a+b) Es gibt also eine ganze Zahl c, nämlich c:=a+b, so dass x+y=2c Daher gilt 2\|x+y und x+y ist gerade. Damit haben wir unseren Satz bewiesen. \darkblue\ Für unser spezielles Beispiel heißt das: \darkblue\ Durch Einsetzen und Ausklammern erhalten wir: \darkblue\ 4+6=2*2+2*3=2*(2+3) \darkblue\ Es gibt also eine ganze Zahl c, nämlich c:=2+3, so dass 4+6=2*5 \darkblue\ Daher gilt 2\|x+y und x+y ist gerade. Wir haben den Satz allgemein und mit zwei beliebigen ganzen geraden Zahlen bewiesen. \big\2.Beispiel: Wir beweisen die Gültigkeit der dritten binomischen Formel. (a-b)*(a+b)=a*a+a*b-b*a-b*b |=a^2+a*b-b*a-b^2 |=a^2-b^2 Es gilt also: \big \red\ (a-b)*(a+b)=a^2-b^2 \big\ 3.Beispiel Man beweise die Behauptung: Das Quadrat einer ungeraden natürlichen Zahl n ist ungerade. n sei eine ungerade Zahl. Somit lässt sich n eindeutig als n=2k+1 darstellen (k ist eine natürliche Zahl, einschließlich der 0). Daraus folgert man: n^2=(2k+1)^2=4k^2+4k+1=2*(2k^2+2k)+1 => n^2 ist ungerade, weil aus k\el\IN_0 leicht (2k^2+2k)\el\IN_0 folgt. \big\ 4.Beispiel Man beweise: Das Quadrat einer geraden natürlichen Zahl n ist gerade. n sei eine gerade natürliche Zahl. Somit lässt sich n eindeutig als n=2k darstellen (k ist eine natürliche Zahl). Daraus folgert man: n^2=(2k)^2=4k^2=2*2k^2 Da aus k\el\IN leicht 2k^2\el\IN folgt, ist n^2 das Doppelte einer natürlichen Zahl und damit gerade. Jetzt wollen wir noch einige Beispiele für direkte Beweise aus der Mengenlehre liefern, wie im ersten Kapitel versprochen, um die Vielfalt des direkten Beweises deutlich zu machen: \big\ 5. Beispiel: Beweise: Seien A und B Aussagen, dann gilt: A\or\ (A\and\ \not\ B) <=>A. Das hört sich erst einmal sehr schwierig an, aber mit einer Wahrheitstafel kann dies sehr leicht gelöst werden: Schritt für Schritt müssen die Wahrheitswerte eingetragen und jeder Fall betrachtet werden. Wir machen es vor: 1. Schritt: Wir tragen bekannte Wahrheitswerte ein: Tabelle 1 2. Schritt: Auch die Wahrheitswerte der Negation können ohne Probleme eingetragen werden: Tabelle 2 3. Schritt: Wir überlegen uns, was die Konjunktion bedeutet. Dazu können wir in unsere Tabelle im ersten Kapitel schauen oder wir wissen es noch: Tabelle 3 4. Schritt: Was bedeutet das "Oder"?: Tabelle 4 5. Schritt: Nun bleibt noch die Äquivalenz zu untersuchen. Das bedeutet, wir müssen schauen, ob die in vorigen Tabelle fett markierten Wahrheitswerte übereinstimmen: Tabelle 5 Es stimmt also alles überein. Und damit ist die Aussage bewiesen. Dieses schrittweise Verfahren müssen wir nun aber üben: \big\ 6. Beispiel: Beweise mit Hilfe von Wahrheitstafeln die folgenden Aussagen: a) \not\ (A\and\ B) <=>\not\ A\or\ \not\ B b) \not\ (A\or\ B) <=>\not\ A\and\ \not\ B c) A\and\ (A=>B)=>B d) (A=>B) <=> (\not\ A\or\ B) e) (A<=>B) <=> (A=>B)\and\ (B=>A) a) und b) stellen die sogenannten De Morgansche Gesetze dar. Da man ganz einfach, so wie oben beschrieben, vorgehen kann, zeigen wir hier nur die fertigen Wahrheitstafeln auf, aber auch das, was wir zuletzt vergleichen müssen: a) Tabelle a) b) Tabelle b) c) Tabelle c) d) Tabelle d) e) Tabelle e) So, nun haben wir also Beweise mit Wahrheitstafeln bewiesen. Die Aussagen wurden durch logische Schlussfolgerungen bewiesen. Wir fassen zusammen: Beim direkten Beweis beweist man die Aussage durch logische Schlussfolgerungen. Genau dies wollen wir anhand der Mengenlehre tun: \big\ 7. Beispiel: Zeige folgendes: a) A\cut\ (B\union\ C)=(A\cut\ B)\union\ (A\cut\ C) b) A\union\ (B\cut\ C)=(A\union\ B)\cut\ (A\union\ C) Seien A\subsetequal\Omega und B\subsetequal\Omega, dann gilt: c) A\cut\ B=\0 =>A\subsetequal\Omega\\B d) A\subsetequal\Omega\\B <=>B\subsetequal\Omega\\A \ a)#Zu zeigen ist aufgrund der Definition der Verknüpfungen \align\ x\el\ A\cut\ (B\union\ C)><<=>x\el\ (A\cut\ B)\union\ (A\cut\ C): x\el\ A\cut\ (B\union\ C)><<=>x\el\ A\and\ x\el\ (B\union\ C) <=>x\el\ A\and\ (x\el\ B\or\ x\el\ C) <=>(x\el\ A\and\ x\el\ B)\or\ (x\el\ A\and\ x\el\ C) <=>x\el\ (A\cut\ B)\or\ x\el\ (A\cut\ C) <=>x\el\ (A\cut\ B)\union\ (A\cut\ C) \b)#Zu zeigen ist aufgrund der Definition der Verknüpfungen \align\ x\el\ A\union\ (B\cut\ C)><<=>x\el\ (A\union\ B)\cut\ (A\union\ C): x\el\ A\union\ (B\cut\ C)><<=>x\el\ A\or\ x\el\ (B\cut\ C) <=>x\el\ A\or\ (x\el\ B\and\ x\el\ C) <=>(x\el\ A\or\ x\el\ B)\and\ (x\el\ A\or\ x\el\ C) <=>x\el\ (A\union\ B)\and\ x\el\ (A\union\ C) <=>x\el\ (A\union\ B)\cut\ (A\union\ C) Kleine Anmerkung: Bei den Beweisen zu den Aufgaben a) und b) haben wir die Distributivgesetze der Aussagenlogik verwendet. c) Zu zeigen ist: x\el\ A =>x\el\Omega\\B. x\el\ A =>x\el\Omega, da A\subsetequal\Omega und x\notel\ B, da A\cut\ B=\0 Aus diesen beiden Erkenntnissen folgt nun x\el\Omega\\B. d) Zu zeigen ist: "=>": x\el\ B=>x\el\Omega\\A. x\el\ B =>x\el\Omega, da B\subsetequal\Omega und x\notel\ A, da A\subsetequal\Omega\\B Aus diesen beiden Erkenntnissen folgt nun x\el\Omega\\A. Für die andere Richtung müssen wir zeigen, dass x\el\ A=>x\el\Omega\\B. x\el\ A =>x\el\Omega, da A\subsetequal\Omega und x\notel\ B, da B\subsetequal\Omega\\A Aus diesen beiden Erkenntnisse folgt nun x\el\Omega\\B. \big\ 8. Beispiel: Um die folgenden zwei Beweise zu verstehen, müssen wir zunächst den Begriff der Fakultät und des Binomialkoeffizienten einführen: Für n, k\el\ \IN_0 setzen wir: n!:=cases(1,n=0;produkt(i,i=1,n),sonst) und (n;k):=cases(n!/((n-k)!*k!),0<=k<=n;0,sonst) Zum Beispiel ist also 3! =3*2*1=6 oder (3;2)=3!/((3-2)!*2!)=(3*2*1)/(2*1)=3. Nun sind wir gewappnet, folgendes zu beweisen: Es seien k, n\el\ \IN mit 1<=k<=n. Dann ist (n;k)=(n-1;k-1)+(n-1;k). Dies kann man durch direktes Nachrechnen leicht zeigen: Wir rechnen die rechte Seite einfach aus: (n-1;k-1)+(n-1;k)=(n-1)!/((n-1-k+1)!*(k-1)!)+(n-1)!/((n-1-k)!*k!) =(n-1)!/((n-k)!*(k-1)!)+(n-1)!/((n-1-k)!*k!) Jetzt bedenken wir, dass wir ja am Ende irgendwas stehen haben wollen wie (n;k)=n!/((n-k)!*k!). Wir bringen die beiden Brüche also auf den Hauptnenner (n-k)!*k! . =(\*) (k(n-1)!)/((n-k)!*k!)+((n-k)*(n-1)!)/((n-k)!*k!) =(k(n-1)!+(n-k)*(n-1)!)/((n-k)!*k!)=(n(n-1)!)/((n-k)!*k!)=n!/((n-k)!*k!)=(n;k) Wir hoffen, dass jeder von euch den Schritt (\*) versteht? Eigentlich ganz einfach, man muss nur folgendes bedenken: k/k! =k/(k(k-1)!)=1/(k-1)! bzw. (n-k)/((n-k)!)=(n-k)/((n-k)*(n-k-1)!)=1/((n-k-1)!) Alles klar? \big\ 9. Beispiel: Mit derselben Idee wie in Beispiel 8 zeigen wir nun noch: (n;k)+(n;k+1)=(n+1;k+1). Wir rechnen auch hier die linke Seite einfach aus: (n;k)+(n;k+1)=n!/((n-k)!*k!)+n!/((n-k-1)!*(k+1)!) =((k+1)*n!)/((n-k)!*(k+1)!)+((n-k)*n!)/((n-k)!*(k+1)!)=((k+1)*n!+(n-k)*n!)/((n-k)!*(k+1)!) =(n!(k+1+n-k))/((n-k)!*(k+1)!)=((n+1)*n!)/((n-k)!*(k+1)!)=((n+1)!)/((n-k)!*(k+1)!)=(n+1;k+1). Damit ist alles gezeigt. Das war der direkte Beweis. Was wir eben gerade (in Beispiel 9) bewiesen haben, ist das Bildungsgesetz im Pascalschen Dreieck. Schaut euch diese Bilder mal an und sucht nach Auffälligkeiten. Ihr werdet erstaunt sein, was im Pascalschen Dreiecks alles so versteckt ist. Siehe dazu auch einen Artikel auf mathematik.de bzw. auf wikipedia.de. Pascalsche Dreieck 1 Pascalsche Dreieck 2
2.2 Der indirekte Beweis Der indirekte Beweis ist einer der elegantesten und auch einfachsten Beweise. Man geht dabei so vor: 1. Man geht einfach vom Gegenteil aus 2. Man versucht dann den Beweis zu einem Widerspruch zu führen 3. Da der Beweisgang legitim und logisch war, muss die Annahme falsch gewesen sein, also folgt die Behauptung des Satzes. Wir betrachten einige Beispiele: \big\ Beispiel 1: \big\ \red\ Behauptung: sqrt(2) ist nicht rational. Wir führen den Beweis indirekt. Nehmen also das Gegenteil an und führen dies zu einem Widerspruch. \big\ \darkblue\ Annahme: sqrt(2) ist rational. Wenn sqrt(2) rational ist, dann lässt sie sich als Bruch zweier ganzer Zahlen p und q darstellen. Also sqrt(2)=p/q . Dabei seien p, q schon gekürzt, insbesondere also teilerfrei. Nun können wir sqrt(2)=p/q umschreiben zu 2=p^2/q^2 <=> p^2=2*q^2 (1). Daraus ergibt sich, dass p gerade ist. Damit lässt sich p also auch als 2*n (wobei n\el\ \IN) schreiben. Einsetzen in (1) liefert: (2n)^2=2*q^2 <=> 4*n^2=2*q^2 <=> 2*n^2=q^2. Hieraus ergibt sich, dass auch q gerade ist. Insbesondere haben p und q damit den gemeinsamen Teiler 2. Wir hatten aber angenommen, dass p und q teilerfrei sind. Das ist ein Widerspruch zu unserer Annahme. Und da eine Behauptung entweder richtig oder falsch ist, folgt die Richtigkeit der Behauptung. Raffiniert oder? \big\ Beispiel 2: Jetzt zu einem Beweis, den Euklid angab. Es gibt durchaus viele Möglichkeiten die folgende Behauptung zu beweisen (so stehen in "Das Buch der Beweise" [ein sehr lesenswertes Buch!] insgesamt sechs verschiedene Beweise für die folgende Behauptung.), aber dennoch wollen wir den Widerspruchsbeweis von Euklid angeben: \big\ \red\ Behauptung: Es gibt unendlich viele Primzahlen. Wir führen den Beweis indirekt. Nehmen also das Gegenteil an und führen dies zu einem Widerspruch. \big\ \darkblue\ Annahme: Es gibt nur endlich viele Primzahlen. Wenn es nur endlich viele Primzahlen geben würde, dann könnten wir diese in einer endlichen Menge {p_1, p_2, ..., p_r } von Primzahlen zusammenfassen. Nun können wir eine neue Zahl konstruieren, indem wir die Primzahlen multiplizieren und 1 addieren. Diese neue Zahl sei n:=p_1*p_2*...*p_r +1 und p sei ein Primteiler von n. Man sieht aber, dass p von allen p_i verschieden ist, da sonst p sowohl die Zahl n als auch das Produkt p_1*p_2*...*p_r teilen würde, somit auch die 1, was nicht sein kann. Und hier haben wir unseren Widerspruch! Es kann also nicht endlich viele Primzahlen geben. Damit muss es unendlich viele Primzahlen geben. Vielleicht war das etwas zu viel des Guten: Hier nochmal etwas langsamer für diejenigen, die mit den obigen Ausführungen nicht so recht etwas anfangen konnten: Wenn der Satz nicht gilt, dann gibt es nur endlich viele Primzahlen: p_1=2; p_2=3; p_3=5; p_4=7; p_5=11; ...; p_r, wobei p_r die größte Primzahl sei. Man bildet das Produkt aller Primzahlen und addiert 1: n:=p_1*p_2*p_3*p_4*p_5*...*p_r +1 Die entstehende Zahl n ist keine Primzahl, weil sie größer ist als die größte Primzahl p_r. Sie muss sich daher aus den Primzahlen p_1, p_2,..., p_r multiplikativ zusammensetzen. n muss daher durch mindestens eine der Primzahlen p_1, p_2,..., p_r teilbar sein. Anderseits erkennt man bei Division von n durch eine Primzahl, dass n wegen der Addition von 1 durch keine Primzahl teilbar ist. \blitz (Anmerkung: Wenn man einen Widerspruch andeuten will, dann setzt man den Pfeil \blitz.)
by FlorianM
[Edit]
2.3 Konstruktive Beweise Betrachten wir einfach mal die Funktion f(x)=x^3-x^2+x-1. Wir behaupten, dass die Funktion eine Nullstelle besitzt. Nun gibt es zwei Möglichkeiten, dies nachzuweisen. Entweder wir geben die Nullstelle x_N direkt an und zeigen, dass f(x_N)=0 gilt (konstruktiv) oder wir argumentieren mit Sätzen, die wir in Kapitel 7 lernen werden, dass eine Nullstelle existieren muss (nicht-konstruktiv). Betrachten wir einmal den Funktionsgraphen der Funktion: Konstruktiver Beweis \big\ 1. Möglichkeit: Konstruktiver Beweis: Durch kurzes Betrachten der Funktion bzw. seines Funktionsgraphen stellen wir fest, dass x_N=1 eine Nullstelle der Funktion ist. Wir weisen dies konstruktiv__ durch Einsetzen nach. Es gilt f(1)=1^3-1^2+1-1=0. Damit haben wir die Nullstelle direkt angegeben und durch Einsetzen gezeigt, dass x_N=1 wirklich eine Nullstelle der Funktion ist. \big\ 2. Möglichkeit: Nicht-konstruktiver Beweis: Ein andere Möglichkeit die Behauptung (Die Funktion besitzt eine Nullstelle) zu beweisen ist, der nicht-konstruktive__ Weg. D.h. wir geben die Nullstelle nicht an, sondern zeigen nur, dass eine Nullstelle existiert. Hierbei wenden wir den so genannten Zwischenwertsatz der Differentialrechnung an, den wir in Kapitel 6 einführen. Dieser besagt: Sei f:[a,b]->\IR eine stetige Funktion. Sei weiterhin f(a)<0 und f(b)>0. Dann existiert ein \xi\el\ (a,b) mit f(\xi)=0. Folgendes Bild soll dies verdeutlichen. Nicht-konstruktiver Beweis Unsere Funktion ist stetig (was das genau bedeutet, erklären wir euch in Kapitel 6, jetzt erstmal glauben). Die Voraussetzung für den Zwischenwertsatz ist also erfüllt. Des Weiteren gilt (siehe auch Zeichnung) f(-1)=(-1)^3-(-1)^2-1-1=-4<0 und f(2)=2^3-2^2+2-1=5>0. Daher muss im Intervall [-1,2] nach dem Zwischenwertsatz eine Nullstelle existieren. Wir können diese aber mit Hilfe des Satzes nicht genau angeben, wir wissen nur, dass eine existiert! Wir hoffen, der Unterschied dieser beiden Methoden ist deutlich geworden.
by FlorianM
[Edit]
2.4 Vollständige Induktion Jeder von Euch hat sicherlich schon mal Domino-Day gesehen. Wenn dem doch nicht so ist und ihr aber zufällig mal reinschaut, dann werdet ihr eventuell eine vollständige Induktion sehen. Das Prinzip der vollständigen Induktion kann man mit dem Umfallen von Dominosteinen vergleichen. Wenn der Anfangsstein fällt, fallen auch alle anderen! Also wenn die Aussage A(n) (für ein n_0) gilt dann gilt es auch für den Nachfolger, also für A(n+1). Die nachfolgenden Dominosteine (n+1) fallen aber nur dann, wenn die Reihe der Dominosteine richtig aufgebaut wurde. Wenn zum Beispiel der Abstand von einem zum anderen Stein zu groß ist, dann kann der andere Stein auch nicht fallen und damit wäre die Induktion zu Ende. Eine Art Herleitung und Erklärung der vollständigen Induktion gibt es schon in dem alten Artikel "Die Beweisverfahren". Wir möchten uns der vollständigen Induktion nun mit Hilfe der Peano-Axiome annähern, die folgendes besagen: Die natürlichen Zahlen können durch die folgenden Axiome charakterisiert werden: • Jede natürliche Zahl n hat einen Nachfolger. Zu jedem n existiert also ein n+1. • 1 ist die kleinste natürliche Zahl. • Jede nichtleere Teilmenge der natürlichen Zahlen besitzt ein kleinstes Element. • Zwischen zwei natürlichen Zahlen liegen nur endlich viele weitere natürliche Zahlen. • Durch Abzählung, beginnend bei 1, durchläuft man in Einerschritten alle natürlichen Zahlen. Diese Peano-Axiome macht man sich bei der vollständigen Induktion zunutze. A(n) sei eine Aussage, die für alle natürlichen Zahlen n>=n_0 getroffen wird. \darkblue\ \- Man zeigt zuerst, dass die Aussage für n_0 gilt (Induktionsanfang) \darkblue\ \- Man zeige, dass wenn A(n) gilt, auch A(n+1) gültig ist (Induktionsschritt) Und das ist der ganze Trick bei der vollständigen Induktion. Denn wenn man zeigt, dass die Aussage auch für den entsprechenden Nachfolger gilt, hat man die Aussage für alle n bewiesen. Um dies nochmals zu verdeutlichen, sei euch dieser Artikel ans Herz gelegt. Wir müssen nun einige Beispiele behandeln, damit das klar wird und werden uns zunächst dabei auf die klassischen Beispiele beschränken. Darüber hinaus werdet ihr sehen, dass die Induktion weite Anwendungen findet und dass dieses Hilfsmittel eine breite Anwendung in der Mathematik hat. Beispiel 1: Beweise: Für alle n\el\ \IN gilt: sum(i,i=1,n)=(n(n+1))/2. \darkblue\ Beweis: \light\ Induktionsanfang für n=1 sum(i,i=1,1)=1 (linke Seite) und (1(1+1))/2=2/2=1 (rechte Seite) Beide Seiten stimmen überein. Der Induktionsanfang ist erfüllt. \light\ Induktionsschritt: Von n auf n+1: Dabei sei sum(i,i=1,n)=(n(n+1))/2 wahr. \light\(Induktionsvoraussetzung) Zu zeigen ist also, dass gilt: sum(i,i=1,n+1)=((n+1)(n+1+1))/2=((n+1)(n+2))/2 sum(i,i=1,n+1)=sum(i,i=1,n)+(n+1)=(n(n+1))/2+(n+1)=(n(n+1)+2*(n+1))/2 =((n+1)(n+2))/2 Und genau dies hatten wir zu zeigen. Beispiel 2: Zeige: Die Summe der ersten n ungeraden natürlichen Zahlen ist n^2. Also: sum((2k-1),k=1,n)=n^2 (Alternativ kann auch sum((2k+1),k=0,n-1)=n^2 gezeigt werden.) \darkblue\ Beweis: \light\ Induktionsanfang für n=1 sum((2k-1),k=1,1)=2*1-1=1 (linke Seite) und 1^2=1 (rechte Seite) Beide Seiten stimmen überein. Der Induktionsanfang ist erfüllt. \light\ Induktionsschritt: Von n auf n+1: Dabei sei sum((2k-1),k=1,n)=n^2 wahr. \light\(Induktionsvoraussetzung) Zu zeigen ist also, dass gilt: sum((2k-1),k=1,n+1)=(n+1)^2 sum((2k-1),k=1,n+1)=sum((2k-1),k=1,n)+2(n+1)-1=n^2+2(n+1)-1 =n^2+2n+2-1=n^2+2n+1=(n+1)^2. Und genau dies mussten wir zu zeigen. Beispiel 3: Bernoullische Ungleichung Beweise: Für n\el\ \IN, a\el\ \IR gilt: (1+a)^n>=1+na. \darkblue\ Beweis: \light\ Induktionsanfang für n=1 (1+a)^1>=1+1*a <=> 1+a>=1+a Beide Seiten stimmen überein bzw. wir erhalten eine wahre Aussage, da ja auch die Gleichheit zugelassen wird. Der Induktionsanfang ist damit erfüllt. \light\ Induktionsschritt: Von n auf n+1: Dabei sei (1+a)^n>=1+na wahr. \light\(Induktionsvoraussetzung) Zu zeigen ist also, dass gilt: (1+a)^(n+1)>=1+(n+1)a (1+a)^(n+1)=(1+a)^n*(1+a)>=(1+na)*(1+a) =1+na+a+na^2=1+(n+1)a+na^2 Da nun na^2>=0 gilt, folgt: 1+(n+1)a+na^2>=1+(n+1)a Tja, und das hatten wir zu zeigen! Also haben wir die Bernoullische Ungleichung bewiesen. Beispiel 4: Zeige: Für n\el\ \IN, n>=5 gilt: 2^n>n^2. \darkblue\ Beweis: \light\ Induktionsanfang für n=5 2^5=32>25=5^2 Wahre Aussage. Der Induktionsanfang ist also erfüllt. \light\ Induktionsschritt: Dabei sei 2^n>n^2 wahr. \light\(Induktionsvoraussetzung) Zu zeigen ist also, dass gilt: 2^(n+1)>(n+1)^2 2^(n+1)=2*2^n>2n^2=n^2+n^2>=\void^\*\.n^2+2n+1=(n+1)^2 \void^\* Hier nutzen für aus, dass für n>=3 gilt: n^2>=2n+1. Dies kann ebenfalls mit vollständiger Induktion bewiesen werden. Also sind wird fertig. Beispiel 5: Für alle n>=4 gilt: n!>2^n . \big\ Beweis mit vollständiger Induktion: \light\ Induktionsanfang für n=4 4! =4*3*2*1=24 >2^4=16 Der Induktionsanfang ist damit erbracht. \light\ Induktionsschritt: Von n auf n+1 Zu zeigen ist, dass (n+1)!>2^(n+1) unter der Induktionsvoraussetzung (IV), dass n!>2^n für ein n bewiesen ist. Wir starten: (n+1)! =(n+1)*n! > (IV) (n+1)*2^n>2^(n+1)=2*2^n . Den letzten Schritt verifizieren wir noch etwas: (n+1)*2^n > 2*2^n n+1 > 2 n >1, was offenbar wahr ist. Beispiel 6: Für dieses Beispiel wollen wir noch das Summen- und Produktzeichen einführen, wenn ihr es noch nicht kennen solltet. Damit man nicht so viel schreiben muss, schreibt man 1+2+3+4+5 als sum(k,k=1,5). k durchläuft nacheinander die natürlichen Zahlen von 1 bis 5 und diese Zahlen werden dann aufsummiert. So ist zum Beispiel sum(k^2,k=1,5)=1^2+2^2+3^2+4^2+5^2 . Analoges gilt für das Produktzeichen. 1*2*3*4*5 schreibt man als produkt(k,k=1,5) und produkt(k^2,k=1,5) bedeutet 1^2*2^2*3^2*4^2*5^2. Was heißt produkt(2k-1,k=1,11)? Oft ist es hilfreich, den Laufindex zu verschieben. So gilt zum Beispiel sum(a_k,k=1,n+1)=sum(a_k,k=1,n)+a_(n+1) oder aber auch produkt(a_k,k=1,n+1)=produkt(a_k,k=1,n)*a_(n+1) . Nun genug der Einführung. Was wollen wir zeigen? Wir wollen zeigen, dass für alle n\el\IN mit n>=2 gilt: sum((2*k-3)/(3^k),k=2,n)=1/3-n/3^n . \light\ Induktionsanfang für n=2 Für die linke Seite erhalten wir sum((2*k-3)/(3^k),k=2,2)=(2*2-3)/(3^2)=(4-3)/9=1/9 und für die rechte Seite 1/3 -2/3^2=3/9 - 2/9 = 1/9 Der Induktionsanfang ist damit also erbracht. \light\ Induktionsschritt: Von n auf n+1 Wir müssen nun zeigen, dass sum((2*k-3)/(3^k),k=1,n+1)=1/3 - (n+1)/3^(n+1) und zwar unter der Induktionsvoraussetzung (IV), dass sum((2*k-3)/(3^k),k=2,n)=1/3-1/3^n für ein n schon bewiesen ist. Hier wenden wir jetzt die Indexverschiebung an, die wir oben besprochen haben. Dies bietet sich bei Summen und Produkten sehr oft an: sum((2*k-3)/(3^k),k=1,n+1)=sum((2*k-3)/(3^k),k=2,n)+(2(n+1)-3)/(3^(n+1)). Nun folgt mit (IV): =1/3 - n/3^n + (2*n+2-3)/(3^(n+1))=1/3 - n/3^n +(2*n-1)/(3^(n+1))=1/3 - (3*n)/(3^(n+1))+(2*n-1)/(3^(n+1))=1/3 - (n+1)/(3^(n+1)) \bigbox Beispiel 7: Nun noch ein Beispiel, mit dem wir das Summenzeichen und die Fakultät nochmals einüben wollen: Behauptung: \forall\ n\el\ \IN: sum(k(k!),k=0,n)=(n+1)!-1. \light\ Induktionsanfang für n=0 bzw. n=1 n=0: sum(k,k=0,0)=0*0! =0*1=0 = (0+1)!-1=1!-1=1-1=0 n=1: sum(k,k=0,1)=0*0!+1*1! =1 = (1+1)!-1=2-1=1 Der Induktionsanfang ist damit erbracht. \light\ Induktionsschritt: Von n auf n+1 Wir müssen zeigen, dass sum(k(k!),k=1,n+1)=(n+2)!-1 unter der Induktionsvoraussetzung (IV), dass sum(k(k!),k=0,n)=(n+1)!-1 für ein n schon bewiesen ist. Mittels Indexverschiebung: sum(k(k!),k=1,n+1)=sum(k(k!),k=1,n)+(n+1)((n+1)!)= (IV) (n+1)!-1+(n+1)!(n+1) =(n+1)!(1+n+1)-1=(n+2)(n+1)!-1=(n+2)!-1. Damit ist auch die Aufgabe gelöst. Beispiel 8: Als weiteres und letztes Beispiel wollen wir den (binomischen Lehrsatz)__ beweisen. Dieser lautet (x+y)^n=sum((n;k)*x^(n-k)*y^k,k=0,n). Wir setzen mit Induktion an: \light\ Induktionsanfang: Für n=0 ergibt sich: (x+y)^0=1= sum((0;k)*x^(0-k)*y^k,k=0,0)=(0;0)*x^(0-0)*y^0=(0;0)*1*1=1 Wir führen den Induktionsanfang nochmals für n=1 durch: (x+y)^1=x+y = sum((1;k)*x^(1-k)*y^k,k=0,1)=(1;0)*x*y^0+(1;1)*x^0*y^1=x+y \light\ Induktionsschritt: Von n auf n+1: Wir müssen zeigen, dass (x+y)^(n+1)=sum((n+1;k)*x^(n+1-k)*y^k,k=0,n+1) und zwar unter der Induktionsvoraussetzung (IV), dass (x+y)^n=sum((n;k)*x^(n-k)*y^k,k=0,n) für ein n schon bewiesen ist. (x+y)^(n+1) = (x+y)^n * (x+y)^1 Mit der Induktionsvoraussetzung ergibt such nun: = (x+y)^1 * sum((n;k)*x^k*y^(n-k),k=0,n) =x*sum((n;k)*x^k*y^(n-k),k=0,n) + y*sum((n;k)*x^k*y^(n-k),k=0,n) =sum((n;k)*x*x^k*y^(n-k),k=0,n) + sum((n;k)*x^k*y*y^(n-k),k=0,n) =sum((n;k)*x^(k+1)*y^(n-k),k=0,n) + sum((n;k)*x^k*y^(n+1-k),k=0,n) Wir substituieren\|k'=k+1 =sum((n;k'-1)*x^k'*y^(n+1-k'),k'=1,n+1) + sum((n;k)*x^k*y^(n+1-k),k=0,n) =(n;0)*x^0 * y^(n+1) + sum(((n;k-1)+(n;k))*x^k*y^(n+1-k)+(n;n)*x^(n+1)*y^0,k=1,n) Mit (n;k)+(n;k-1)=(n+1;k) folgt die Behauptung. Als Übungsaufgabe vervollständigt bitte den Beweis. Ein Spezialfall des binomischen Lehrsatz ist zum Beispiel die erste binomische Formel für n=2. Wir erhalten demnach: (x+y)^2=sum((2;k)*x^(2-k)*y^k,k=0,2)=(2;0)*x^2*y^0+(2;1)*x^1*y^1+(2;2)*x^0*y^2 =x^2+2*x*y+y^2 Weiter erhält man: (x+y)^0=1 (x+y)^1=x+y (x+y)^2=x^2+2*x*y+y^2 (x+y)^3=x^3+3*x^2*y+3*x*y^2+y^3 (x+y)^4=x^4+4*x^3*y+6*x^2*y^2+4*x*y^3+y^4 usw. Das Schöne ist, dass wir uns das gar nicht alles merken brauchen, denn wenn wir den binomischen Lehrsatz kennen, dann können wir uns alles ohne Probleme in ein paar Minuten herleiten. Und die Koeffizienten solltet ihr alle im Pascalschen Dreieck wiederfinden. :) \blue\ Wem der Beweis des binomischen Lehrsatzes zu schnell ging, hier nochmal eine ausführlichere Version des Induktionsschrittes: \blue\ (x+y)^(n+1)=(x+y)*(x+y)^n=(x+y)*sum((n;k)*x^(n-k)*y^k,k=0,n) \blue\ =(x+y)*[(n;0)*x^n+(n;1)*x^(n-1)*y+(n;2)*x^(n-2)*y^2 \blue\ +...+(n;n)*y^n] \blue\ =(n;0)*x^(n+1)+(n;0)*x^n*y+(n;1)*x^n*y+(n;1)*x^(n-1)*y^2 \blue\ +...+(n;n)*x*y^n+(n;n)*y^(n+1) \blue\ =x^(n+1)+[(n;0)+(n;1)]*x^n*y+[(n;1)+(n;2)]*x^(n-1)*y^2 \blue\ +...+[(n;n-1)+(n;n)]*x*y^n+y^(n+1) \blue\ =(n+1;0)*x^(n+1)+(n+1;1)*x^n*y+(n+1;2)*x^(n-1)*y^2 \blue\ +...+(n+1;n)*x*y^n+(n+1;n+1)*y^(n+1) \blue\ =sum((n+1;k)*x^(n+1-k)*y^k,k=0,n+1) Auch hier eine Übungsaufgabe. Natürlich müsst ihr viel mehr Aufgaben zur vollständigen Induktion rechnen. Sucht euch einfach alte Klausuren oder schlagt ein Buch auf und macht euch mit dem Verfahren der vollständigen Induktion vertraut. \big\ \red\ Aufgabe 1: Beweise die verallgemeinerte Bernoullische Ungleichung produkt((1+x_k),k=1,n)>=1+sum(x_k,k=1,n). \ \big\ \red\ Aufgabe 2: Beweise die geometrische Summenformel a^(n+1)-b^(n+1)=(a-b)*sum(a^k*b^(n-k),k=0,n). \big\ \red\ Aufgabe 3: Man zeige: n^2+n ist eine gerade(d.h durch 2 teilbare) Zahl \forall\ n\el\ \IN \big\ \red\ Aufgabe 4: Man zeige: n^3-6n^2+14n ist durch 3 teilbar \forall\ n\el\ \IN \big\ \red\ Aufgabe 5 (Klassiker!): n Elemente kann man auf n! verschiedenen Arten anordnen. \big\ \red\ Aufgabe 6(verallgemeinerte Dreiecksungleichung: Für ein beliebiges n\el\ N und reelle Zahlen a_1, a_2,.., a_n \el\R gilt: | | abs(sum(a_k,k=1,n))<=sum(abs(a_k),k=1,n) \big\ \red\ Aufgabe 7: Beweise per vollständiger Induktion: | | 4^1*4^2*4^3*...*4^n=produkt(4^k,k=1,n)=2^(n*(n+1)) \lr(1)| | \forall n>=1
by FlorianM
[Edit]
2.5 Lösungen zu den Übungsaufgaben \big\ \red\ Lösung zu Aufgabe 1: Beweise die verallgemeinerte Bernoullische Ungleichung produkt((1+x_k),k=1,n)>=1+sum(x_k,k=1,n). \light\ Induktionsanfang für n=1: produkt((1+x_k),k=1,1)=1+x_1 >= 1+sum(x_k,k=1,1)=1+x_1 Da auch bei der Ungleichung die Gleichheit zugelassen ist, ist der Induktionsanfang erbracht. \light\ Induktionsschritt: Von n auf n+1: Zu zeigen ist produkt((1+x_k),k=1,n+1)>=1+sum(x_k,k=1,n+1) unter der Induktionsvoraussetzung (IV), dass produkt((1+x_k),k=1,n)>=1+sum(x_k,k=1,n) für ein n bewiesen ist. produkt((1+x_k),k=1,n+1)=(produkt((1+x_k),k=1,n))*(1+x_(n+1)) >= (IV) (1+sum(x_k,k=1,n+1))*(1+x_(n+1)) >=1+x_(n+1)+sum(x_k,k=1,n)+x_(n+1)*sum(x_k,k=1,n)=1+sum(x_k,k=1,n+1)+x_(n+1)*sum(x_k,k=1,n) >=1+sum(x_k,k=1,n+1), da x_(n+1)*sum(x_k,k=1,n) >=0. Damit ist alles gezeigt. \big\ \red\ Lösung zu Aufgabe 2: Beweise die geometrische Summenformel a^(n+1)-b^(n+1)=(a-b)*sum(a^k*b^(n-k),k=0,n). Diese kann mittels vollständiger Induktion bewiesen werden. \light\ Induktionsanfang: n=0 a^(0+1)-b^(0+1)=(a-b)*sum(a^k*b^(0-k),k=0,0) a^1-b^1=(a-b)*(a^0*b^(0-0)) a-b=(a-b)*1 a-b=a-b Der Induktionsanfag ist damit erbracht. \light\ Induktionsschritt: Von n auf n+1 Wir müssen zeigen, dass a^(n+2)-b^(n+2)=(a-b)*sum(a^k*b^(n+1-k),k=0,n+1) gilt und zwar unter der Induktionsvoraussetzung (IV), dass a^(n+1)-b^(n+1)=(a-b)*sum(a^k*b^(n-k),k=0,n) für ein n schon bewiesen ist. (a-b)*sum(a^k*b^(n+1-k),k=0,n+1)=(a-b)*[(sum(a^k*b^(n+1-k),k=0,n))+a^(n+1)*b^(n+1-(n+1))] =(a-b)*[(sum(a^k*b*b^(n-k),k=0,n))+a^(n+1)*b^(n+1-n-1)] =(a-b)*[b*(sum(a^k*b^(n-k),k=0,n))+a^(n+1)*b^0] =(a-b)*[b*(sum(a^k*b^(n-k),k=0,n))+a^(n+1)*1] =b*(a-b)*sum(a^k*b^(n-k),k=0,n)+(a-b)*a^(n+1) Nach der Induktionsvorausetzung folgt: =b*(a^(n+1)-b^(n+1))+(a-b)*a^(n+1) =b*a^(n+1)-b^(n+2)+a^(n+2)-b*a^(n+1) =a^(n+2)-b^(n+2) \bigbox Damit ist alles gezeigt. \big\ \red\ Lösung zu Aufgabe 3: n^2+n ist eine gerade (d.h durch 2 teilbare) Zahl \forall n>=0 \blue\ Beweis__: \light\ Induktionsanfang für n=1: 1^2+1=2 \blue\ ist eine gerade Zahl. \checked \light\ Induktionsvoraussetzung: Es gelte die Induktionsvoraussetzung: n^2+n ist eine gerade Zahl Zu zeigen: Die Behauptung gilt auch für(n+1), also (n+1)^2+(n+1) ist eine gerade Zahl. \light\ Induktionsschluss: (n+1)^2+(n+1)=n^2+2n+1+n+1 | |=n^2+3n+2 | |=(n^2+n)+2*(n+1) das ist eine gerade Zahl, weil der erste Summand gerade ist nach Induktionsvoraussetzung und der zweite Summand ein ganzzahliges Vielfaches von 2 ist. Damit haben wir diese kleine Aufgabe auch gelöst. \big\ \red\ Lösung zu Aufgabe 4: n^3-6n^2+14n ist durch 3 teilbar \forall n>=0 \blue\ Beweis_: \light\ Induktionsanfang für n=0: 0^3-6*0^2+14*0=0 \blue\ ist durch 6 ohne Rest teilbar. \checked \light\ Induktionsvoraussetzung: Es gelte die Induktionsvoraussetzung: n^3-6n^2+14n ist durch 3 teilbar Zu zeigen: Die Behauptung gilt auch für(n+1), also (n+1)^3-6*(n+1)^2+14*(n+1) ist durch 3 teilbar \light\Induktionsschluss: (n+1)^3-6*(n+1)^2+14*(n+1)=(n^3+3n^2+3n+1)-6(n^2+2n+1)+14*(n+1) |=n^3+3n^2+3n+1-6n^2-12n-6+14n+14 |=n^3-3n^2+5n+9 |=n^3-6n^2+14n+3n^2-9n+9 |=(n^3-6n^2+14n)+3*(n^2-3n+3) und wie wir sehen können, ist das durch 3 teilbar, da der erste Summand durch 3 teilbar ist nach IV und der zweite Summand ein ganzzahliges Vielfaches von 3 ist. \bigbox \big\ \red\ Lösung zu Aufgabe 5: n Elemente kann man auf n! verschiedene Arten anordnen. \stress\ Lösung__: Wie kann man das zeigen, wird sich der ein oder andere gefragt haben. Das kann man wieder mit der vollständigen Induktion beweisen. Nun zuerst blättert nochmal etwas weiter nach oben zum Abschnitt, wo wir die Falkultäten eingeführt haben. Wenn ihr das gemacht habt und soweit alles verstanden habt dann können wir loslegen. \light\ Induktionsanfang für n=1 (also ein Element): n=1: 1 Element lässt sich auf eine Art anordnen: 1=1! supi das haben wir! \checked \light\ Induktionsschluss: Nun müssen wir ein wenig allgemeiner werden. Geben wir uns einfach Elemente vor. Gegeben seien die Elemente M_1 bis M_n. Diese lassen sich nach Induktionsvoraussetzung auf n! Arten anordnen. Nun kommt ein neues Element M_(n+1) hinzu. Für die (n+1) Elemente stehen also (n+1) Plätze zur Verfügung. Das Element M_(n+1) kann auf irgendeines dieser (n+1) Plätze gesetzt werden. Für die restlichen Elemente M_1 bis M_n stehen nun noch jeweils n Plätze zur Verfügung. Dafür gibt es nach Induktionsvoraussetzung n! Möglichkeiten. Insgesamt gibt es also für alle Elemente M_1 bis M_(n+1) (n+1)*n! =(n+1)! Möglichkeiten. Der Beweis ist vollzogen und die Aufgabe damit erledigt. \ \big\ \red\ Lösung zu Aufgabe 6: Für ein beliebiges n\el\ N und reelle Zahlen a_1, a_2,.., a_n \el\R gilt: | | abs(sum(a_k,k=1,n))<=sum(abs(a_k),k=1,n) \lr(1) \blue\ Beweis_: \light\ Induktionsanfang für n=1: A(1)=abs(1)<=abs(1)<=>1<=1 | | \checked \light\ Induktionsvoraussetzung: Es gelte die Induktionsvoraussetzung: abs(sum(a_k,k=1,n))<=sum(abs(a_k),k=1,n) Zu zeigen: Die Behauptung gilt auch für(n+1), also | |abs(sum(a_k,k=1,n+1))<=sum(abs(a_k)+abs(a_(n+1)),k=1,n) \light\Induktionsschluss: nach Induktionsvoraussetzung gilt \ref(1): | |abs(sum(a_k,k=1,n+1)) <=abs(sum(a_k,k=1,n))+abs(a_(n+1)) | | <=sum(abs(a_k),k=1,n)+sum(abs(a_(n+1)),k=1,n)<=sum(abs(a_k),k=1,n+1) | |\bigbox \ \big\ \red\ Lösung zu Aufgabe 7: Beweisen Sie per vollständiger Induktion: | | 4^1*4^2*4^3*...*4^n=produkt(4^k,k=1,n)=2^(n*(n+1)) \lr(1)| | \forall n>=1 \blue\ Beweis_: \light\ Induktionsanfang für n=1: linke Seite: 4^1=4 rechte Seite: 2^(1*(1+1))=4 | \checked \light\ Induktionsvoraussetzung: Es gelte die Induktionsvoraussetzung: 4^1*4^2*4^3*...*4^n=produkt(4^k,k=1,n)=2^(n*(n+1)) \light\ Induktionsbehauptung: sollte jetzt klar sein. \light\Induktionsschluss: nach Induktionsvoraussetzung gilt \ref(1): | |produkt(4^k,k=1,n+1)=(produkt(4^k,k=1,n))*4^(n+1)=2^(n*(n+1))*2^(2(n+1)) | |=2^(n^2+n)*2^(2n+2) | |=2^(n^2+3n+2) | |=2^((n+1)*(n+2)) | |\bigbox Ihr seht, die Induktion wird auch bei allgemeinen Beweisen verwendet. Ingenieure bekommen meist Zahlen ;)
by FlorianM
[Edit]
Abschluss und Literatur Das war nun unser zweiter Teil. Das dritte Kapitel wird auch bald folgen und dort werden dann endlich die reellen Zahlen eingeführt. Wir werden alles auf ein mathematisches Fundament stellen, damit wir mit den reellen Zahlen so "rechnen" können, wie wir es von der Schule her gewohnt sind. Einige fragen sich vielleicht, warum wir das nicht jetzt schon können!? Na, dann lest den nächsten Artikel. ;) Als Literaturempfehlung wollen wir diesmal ein englischsprachiges Werk geben und zwar "How to prove it". Denn auch im Studium kommt man nicht herum, englische Literatur zu lesen, denn ab gewissen Semestern gibt es einfach kaum noch deutsche Fachliteratur. Und warum sollten sich die Verlage die Mühe machen, diese Bücher zu übersetzen? ;) Wir wünschen gutes Gelingen. :-) Ein Danke geht natürlich auch wieder zu unseren fleißigen Testlesern.
by FlorianM
[Edit]

Trennlinie

-> §1 Einführung und Grundlagen
-> §2 Die Beweisverfahren
-> §3 Die reellen Zahlen
-> §4 Folgen
-> §5 Reihen
-> §6 Grenzwerte und Stetigkeit
-> §7 Differenzierbarkeit
-> §8 Integration
-> §9 Besondere Reihe
-> §10 Funktionenfolgen (Punktweise und gleichmäßige Konvergenz)

by FlorianM
[Edit]
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfpdf-Datei zum Artikel öffnen, 331 KB, vom 12.10.2008 08:28:31, bisher 6954 Downloads


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Analysis :: Beweistechnik :: Binomialkoeffizienten :: Studium :
Analysis I - §2 Die Beweisverfahren [von da_bounce]  
Zweiter Teil der Artikelserie zur Analysis I. Hier geht es um die Beweisverfahren wie direkter Beweis oder vollständige Induktion. Wir geben sehr viele Beispiele mit ausführlichen (!) Lösungen an.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 19844
 
Aufrufstatistik des Artikels
Insgesamt 4160 externe Seitenaufrufe zwischen 2012.01 und 2022.09 [Anzeigen]
DomainAnzahlProz
https://google.com20%0 %
https://matheplanet.com20%0 %
https://google.de43210.4%10.4 %
http://google.li3518.4%8.4 %
http://google.de287869.2%69.2 %
http://www.stud.uni-hannover.de1222.9%2.9 %
http://google.it681.6%1.6 %
http://google.hr681.6%1.6 %
http://google.fr501.2%1.2 %
http://google.pl491.2%1.2 %
http://google.gr370.9%0.9 %
https://google.ru130.3%0.3 %
http://images.google.de50.1%0.1 %
http://search.conduit.com90.2%0.2 %
http://google.com80.2%0.2 %
https://www.startpage.com40.1%0.1 %
http://duckduckgo.com30.1%0.1 %
http://www.bing.com240.6%0.6 %
http://images.google.com20%0 %
http://google.ch20%0 %
http://just-like.net20%0 %
http://isearch.avg.com30.1%0.1 %
https://duckduckgo.com20%0 %
https://www.bing.com20%0 %
http://suche.t-online.de40.1%0.1 %
http://ecosia.org10%0 %
http://start.mysearchdial.com10%0 %
http://suche.aol.de10%0 %
http://de.search.yahoo.com20%0 %
http://int.search.myway.com10%0 %
http://www.search.ask.com10%0 %
http://avira-int.ask.com10%0 %
http://de.yhs4.search.yahoo.com20%0 %
http://suche.gmx.net20%0 %
https://www.scribbr.de10%0 %
http://www.ask.com10%0 %
http://de.search-results.com10%0 %
http://search.icq.com10%0 %
http://de.ask.com10%0 %
http://www.ecosia.org10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 2 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.09.05-2022.09.22 (2x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 4076 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
201202-02 (351x)http://google.li/url?sa=t&rct=j&q=analysis beweisverfahren konvergenz
2020-2022 (317x)https://google.de/
2013-2017 (306x)http://google.de/url?sa=t&rct=j&q=
201204-04 (295x)http://google.de/url?sa=t&rct=j&q=verschachtelte induktion domino day
201203-03 (264x)http://google.de/url?sa=t&rct=j&q=zwei beweise-mathe
201201-01 (253x)http://google.de/url?sa=t&rct=j&q=vollständige induktion matheraum beispie...
201210-10 (225x)http://google.de/url?sa=t&source=web&cd=1&ved=0CAwQohAwAA
201211-11 (192x)http://google.de/url?sa=t&rct=j&q=vollständige induktion n >=  3 ist n^2 ...
201310-10 (130x)http://google.de/url?sa=t&rct=j&q=summe k^n direkter beweis
2012-2014 (121x)http://www.stud.uni-hannover.de/~fmodler/ganalysisI.html
201410-10 (120x)http://google.de/url?sa=t&rct=j&q=analysis direkter beweis ungleichungen
201411-12 (111x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA
201311-11 (104x)http://google.de/url?sa=t&rct=j&q=hilfe mathe aufgaben und lösungen hannov...
201209-09 (88x)http://google.de/url?sa=t&rct=j&q=mp analysis §2
2020-2022 (79x)https://google.de
201205-05 (69x)http://google.de/url?sa=t&rct=j&q=wichtige beweise analysis
201304-04 (69x)http://google.de/url?sa=t&rct=j&q=wichtigsten sätze analysis 1 mit beweis
201301-01 (68x)http://google.it/imgres?q=pascalsches dreieck
201402-02 (68x)http://google.hr/url?sa=t&rct=j&q=
201305-05 (67x)http://google.de/url?sa=t&rct=j&q=wie mach man 1 beweis ?
201302-02 (60x)http://google.de/url?sa=t&rct=j&q=wichtigsten beweise analysis 1
201307-08 (59x)http://google.de/url?sa=t&rct=j&q=hilfe beim beweisen analysis
201212-12 (52x)http://google.de/url?sa=t&rct=j&q=Zeigen Sie mit Hilfe der vollständigen I...
201401-01 (50x)http://google.fr/url?sa=t&rct=j&q=
201309-09 (49x)http://google.pl/url?sa=t&rct=j&q=
201207-07 (43x)http://google.de/url?sa=t&rct=j&q=teilerfrei
201501-01 (41x)http://google.de/url?sa=t&rct=j&q=zwischenwertsatz und bernoullische ungleich...
201206-06 (40x)http://google.de/url?sa=t&rct=j&q=vollständige induktion von sum from k=1 ...
201303-03 (40x)http://google.de/url?sa=t&rct=j&q=wichtige beweise analysis 1
201404-04 (37x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCsQFjAB
201306-06 (37x)http://google.gr/url?sa=t&rct=j&q=matroids analysis i - §2
201504-04 (34x)http://google.de/url?sa=t&rct=j&q=analysis beweise
202111-11 (33x)https://google.de/url?esrc=s
201502-02 (29x)http://google.de/url?sa=t&source=web&cd=2&ved=0CB4QFjAB
201503-03 (28x)http://google.de/url?sa=t&source=web&cd=6&ved=0CDIQFjAF
201208-08 (26x)http://google.de/url?sa=t&rct=j&q=summenformel k/2^k beweise
201406-06 (20x)http://google.de/url?sa=t&rct=j&q=mathematik beweisen lernen
201510-10 (16x)http://google.de/url?sa=t&rct=j&q=direkter beweis der bernoullischen
202005-05 (13x)https://google.ru/
201511-11 (12x)http://google.de/url?sa=t&source=web&cd=1&rct=j&q=mathe beweise analysis
2016-2017 (11x)http://google.de/
201601-01 (10x)http://google.de/url?sa=t&rct=j&q=mathestoff beweise analysis
201609-09 (6x)http://google.de/url?sa=t&rct=j&q=analysis beweisaufgaben
201612-12 (5x)http://google.de/url?sa=t&rct=j&q=beweisverfahren mathematik
2016-2017 (5x)http://images.google.de/url?sa=t&rct=j&q=
201209-09 (5x)http://search.conduit.com/Results.aspx?q=mathematische beweismethoden&Suggest...
2018-2019 (5x)http://google.com/
201512-12 (5x)http://google.de/url?sa=t&source=web&cd=10&rct=j&q=ungleichungen beweisen ana...
2020-2022 (4x)https://www.startpage.com/
201604-04 (4x)http://google.de/url?sa=t&source=web&cd=1&rct=j&q=analysis nur beweisen

[Top of page]

"Mathematik: Analysis I - §2 Die Beweisverfahren" | 15 Comments
The authors of the comments are responsible for the content.

Re: Analysis I - §2 Die Beweisverfahren
von: Martin_Infinite am: Fr. 04. April 2008 18:20:17
\(\begingroup\) @leser: induktion ist zweifelsohne ein wichtiges beweismittel. aber bei weitem nicht das wichtigste. durch die sture anwendung dieses prinzips werden unnötige denkblockaden gelegt und außerdem weiß man dann genauso wenig wie vorher, wie man einst auf die behauptung gekommen ist. ferner behindert es teilweise das deduktive denken, also neues aus bekanntem zu folgern. jede der oben genannten beispiele kann man ohne induktion behandeln, meistens dann auch noch kürzer und viel instruktiver. \stress\beispiel 1.\normal 2(1+2+...+(n-1)+n) =(1+n)+(2+(n-1))+...+((n-1)+2)+(n+1)=n(n+1) \stress\beispiel 2.\normal 1+3+..+(2n-1)=2(1+2+...+n)-n=n*n \stress\beispiel 3.\normal man muss a >= -1 fordern \(im oben angegebenen induktionsbeweis werden ungleichungen mit a+1 multipliziert\). auch hier eine alternative: für a>=0 ist nach dem binomischen lehrsatz (1+a)^n>=(n;0) + (n;1) a =1+na. nun sei -1<=a<=0. dann ist 0<=-a<=1. nun betrachte (1+a)^n=1-n(-a)+1/2 n(n-1) (-a)^2- 1/6 n(n-1)(n-2) (-a)^3 + ... jeder summand dabei ist dabei betraglich kleiner als der vorige, sodass (1+a)^n>=1-n(-a)=1+na. \stress\beispiel 4.\normal für n >= 5 liefert der binomische lehrsatz 2^n >= (n;0)+(n;1)+(n;2)+(n;n-2)+(n;n-1)+(n;n)=2(1+n+n(n-1)/2) =n^2+n+2 > n^2 \stress\beispiel 5.\normal n! = (n*...*3)*2 > (2*...*2)*2 =2^n. \stress\beispiel 6.\normal zunächst zwei allgemeine formeln: ausmultiplizieren liefert (q-1) sum(q^i,i=0,n) = q^(n+1)-1. fasst man das als polynomiale gleichung auf und leitet formal nach q ab, folgt (n+1) q^n=(q-1) sum(i q^(i-1),i=1,n) + sum(q^i,i=0,n), also sum(i q^(i-1),i=1,n)=((n+1) q^n-(q^(n+1)-1)/(q-1))/(q-1) insbesondere folgt im beispiel sum((2k-3)/(3^k),k=2,n) = 2/3 (sum(k (1/3)^(k-1),k=1,n)-1) - sum((1/3)^k,k=1,n-1)= ... =1/3-n/3^n \stress\beispiel 7. \normal 1*1! + 2*2! + 3*3! + ... + n*n! = (2*1! - 1!)+(3*2! - 2!)+...+((n+1)*n!-n!) =(2!-1)+(3!-2!)+...+((n+1)!-n!)=(n+1)!-1 \stress\beispiel 8.\normal wenn man (x+y)^n ausmultipliziert, ergibt sich die summe aller produkte von n faktoren aus {x,y}. kommt dabei x genau k mal vor, so ist dieses produkt x^k y^(n-k) und es kommt so oft vor, wie man k objekte aus n objekten auswählen kann, also (n;k) mal. \stress\aufgabe 1.\normal auch hier muss man die x_i einschränken, und zwar muss entweder x_i >= 0 für alle i oder -1 <= x_i <= 0 für alle i sein. im ersten fall folgt die ungleichung sofort durch ausmultiplizieren. im zweiten fall betrachte wieder (1+x_1)*...*(1+x_n)=sum(x_1^e_1 ... x_n^e_n,e_i \in menge(0,1)) und vergleiche summanden mit kleinerem totalgrad e_1+...+e_n. \stress\aufgabe 2.\normal ausmultiplizieren liefert (a-b)(a^n + a^(n-1) b + ... + a^1 b^(n-1) + b^n) =a^(n+1) + a^n b + ... + a^2 b^(n-1) + a b^n - a^n b + a^(n-1) b^2 + ... + a b^n + b^(n+1) =a^(n+1)-b^(n+1) \stress\aufgabe 3.\normal n^2+n=n(n+1), entweder n oder n+1 ist gerade. alternativ verwende man beispiel 1. \stress\aufgabe 4.\normal durch differenzenbildung sieht man n^3-6n^2+14n = 3*sum(k^2-3k+3,k=0,n-1). \stress\aufgabe 5.\normal für das erste element gibt es n plätze, für das zweite dann nur noch n-1, usw. und das letzte hat nur noch einen platz. also gibt es n*...*1=n! möglichkeiten. \stress\aufgabe 6.\normal dies gehört zu den aussagen über endlich viele bestandteile, die sofort aus dem fall folgen, wo man genau zwei hat. im induktionsschritt würde man dies dann sehen. aber auch hier instruktiver aufgeschrieben: abs(a_1+...+a_n) <= abs(a_1)+abs(a_2+...+a_n) <= ... <= abs(a_1)+...+abs(a_n) \stress\aufgabe 7.\normal folgt aus beispiel 1. streng genommen kann man nicht mit pünktchen (...) beweisen, allerdings wurden die oben genau dann eingesetzt, wenn es sich um allgemeine sachverhalte handelt \(so etwas wie a_1 + ... + a_n = a_(\sigma_1)+...+a_(\sigma_n) für eine permutation \sigma von {1,...,n}\). letztere muss man natürlich per induktion beweisen, weil eben \IN induktiv definiert ist; aber deren gültigkeit muss vor dem lösen der obigen aufgaben ohnehin abgeklärt sein. aufgaben 4,5,6 geben im gegensatz zu den anderen keine zur induktion alternativen argumente, schreiben sie jedoch ebenfalls instruktiver auf. man sollte die obigen induktionsbeweise nicht als demonstration für die bedeutung der induktion ansehen, sondern nur als erste möglichkeit, sich damit das verfahren einzuprägen, bevor es zu angebrachten anwendungen geht.\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: FlorianM am: Fr. 04. April 2008 18:25:29
\(\begingroup\)Hallo Martin, danke für deine ausführlichen Ergänzungen und ich stimme dir auch in der Meinung zu, dass man nicht blind nur mit Induktion arbeiten sollte. Im Artikel selbst ging es uns aber in erster Linie um die Verdeutlichung des Prinzips der vollständigen Induktion. Deine Ausführung sind aber eine gelungene Ergänzung. Vielen Dank dafür! ;) Gruss Florian\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: Jonathan_Scholbach am: Fr. 04. April 2008 18:55:04
\(\begingroup\)Ihr schreibt \quoteon Wir geben aber auch zu, dass man bei einigen Behauptungen schon eine sehr pfiffige Idee braucht, und es für Anfänger fast unmöglich ist, ohne Hilfe, auf diese Idee zu kommen. Aber nur durch kontinuierliches Üben kann man die Beweismethoden trainieren. \quoteoff Das stimmt. Aber man kann es auch so formulieren: Durch kontinuierliches Üben kann man tatsächlich die Beweismethoden trainieren und sich in beeindruckendem Maße verbessern. In meinen Augen ist das die Hauptbeschäftigung während des Mathestudiums und es ist sehr verblüffend, welche Fortschritte man erzielen kann. Für mich ist es immer am interessantesten, wenn ich einen meiner (zahlreichen) Denkfehler entlarve. Viele Grüße, Jonathan\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: da_bounce am: Fr. 04. April 2008 21:16:10
\(\begingroup\)Hallo Martin, ich schließe mich schon deinen Ausführungen ab aber und jetzt kommt es, dass was du da hingeschrieben hast verstehen maximal 35% der Erstsemestler :) und natürlich gibt es andere Methoden um zum Ziel zu kommen, denn es heißt ja nicht umsonst viele Wege führen nach Rom! Wie FlorianM schon sagte wir wollten die Vorgehensweise der Induktion beschreiben und das ist denke ich gelungen. lg George\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: Redfrettchen am: Fr. 04. April 2008 21:36:48
\(\begingroup\)Hallo, gelungene Fortsetzung des ersten Teils, würde ich sagen :D - auch wenn ich zugegebenermaßen die Induktionsbeispiele und -aufgaben nur großzügig überfolgen habe. Als Anfänger wäre ich wahrscheinlich von dem ersten Produktzeichen bei der Definition der Fakultät erschlagen worden. Wäre es nicht besser gewesen, das induktiv zu erklären (mit Hinweis auf den Text weiter unten)? Grüße! Thomas\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: Wally am: Fr. 04. April 2008 22:57:04
\(\begingroup\)Hallo, ihr beiden, leider seid ihr einer (zugegeben sehr haüfigen) Unsauberkeit aufgesessen. Man unterscheide den indirekten Beweis vom Widerspruchsbeweis. \ Der erste beruht auf (A=>B) <=> (\not B => \not A) der zweite auf (\not A=>f) =>A Bekannte Beispiele sind etwa: Indirekter__ Beweis__ Beh: n^2 gerade => n gerade (A=>B) Bew: Ann: sei n ungerade. (\not B) Dann ist n=2*m+1 und daher n^2=4m^2+4*m+1, also ist n^2 ungerade (\not A) q.e.d. Widerspruchsbeweis__ Beh: \sqrt(2) ist irrational (A) Bew: Ann: \sqrt(2) ist rational. (\not A) (übliche Rechnung) Widerspruch (f) Daher ist \not A falsch und somit A wahr. Viele Grüße Wally \(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: cristiano am: Sa. 05. April 2008 11:11:26
\(\begingroup\)Hallo zusammen Ist ein wirklich guter Artikel, mit guten Beispielen!! Gerade für Anfänger wirklich sehr gut geeignet!! Ihr habt bei der Einführung des "Summenzeichens und des Produktzeichens" (Beweisart: Induktion, Bsp. 6) , beim Verschieben des Laufindex bei den Indizes Fehler gemacht (Laufindex k, aber in der Summe bzw. Produkt immer a_n). Gruss cristiano\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: Xerdon am: Sa. 05. April 2008 15:23:39
\(\begingroup\)Vielen Dank für den tollen Artikel, der einfach schön die ganzen Beweisverfahren zusammenfasst 😄 Gruß Xerdon\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: javra am: Sa. 05. April 2008 19:01:32
\(\begingroup\)Vollständige Induktion beim Domino Day? Wollen sie den Rekord jetzt also doch auf abzählbar unendlich viele Steine erhöhen!\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: sebastiano am: Sa. 31. Mai 2008 01:20:23
\(\begingroup\)Hallo Jungs! Gute Arbeit!!! Gruß Sebastian\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: FlorianM am: Sa. 31. Mai 2008 08:13:28
\(\begingroup\)Danke Sebastian. :) Viele sonnige Grüße nach Düsseldorf! Florian\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: Mathador111 am: Sa. 13. September 2008 18:36:38
\(\begingroup\)Hallo, auch von mir ein großes Lob. Für mich, als einer der gerade den Mathematik Vorkurs belegt, eine sehr sehr schöne Sache eure Artikel. Allerdings ist mir aufgefallen, dass in Kapitel 2 der Beweis zur Anzahl der Elemente einer Potenzmenge fehlt (es wurde zumindest in Kapitel 1 gesagt, dass er in 2 kommen wird unter Vollständige Induktion). viele Grüße, Christian\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: FlorianM am: Sa. 13. September 2008 19:18:13
\(\begingroup\)Hallo Christian, danke für das Lob. Hat uns sehr gefreut. 😄 Das mit dem fehlenden Beweis stimmt. Das haben wir ganz groß in Kapitel 1 angekündigt, dann aber wohl vergessen. Wir werden dies bei Gelegenheit nachholen. Gruss Florian\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: FlorianM am: So. 12. Oktober 2008 08:28:58
\(\begingroup\)Hallo, es steht jetzt auch eine pdf-Datei zur Verfügung. :) Vielen Dank an Redfrettchen! Gruss Florian\(\endgroup\)
 

Re: Analysis I - §2 Die Beweisverfahren
von: mightym0e am: Di. 06. März 2012 19:23:44
\(\begingroup\)\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]