Fraktal

Das Prinzip der vollständigen Induktion

"Seht Euch doch diesen Mathematiker an", sagt der Logiker, "er bemerkt, daß die ersten neunundneunzig Zahlen kleiner als hundert sind und schließt daraus auf Grund von etwas, das er Induktion nennt, daß alle Zahlen kleiner als hundert sind."

"Ein Physiker glaubt", sagt der Mathematiker, "das 60 durch alle Zahlen teilbar ist. Er bemerkt, daß 60 durch 1, 2, 3, 4, 5 und 6 teilbar ist. Er untersucht noch ein paar Fälle wie 10, 20 und 30, die, wie er sagt, aufs Geratewohl herausgegriffen sind. Da 60 auch durch diese teilbar ist, betrachtet er seine Vermutung als hinreichend durch den experimentellen Befund bestätigt."

"Ja, aber seht Euch doch die Ingenieure an", sagt der Physiker. "Ein Ingenieur hatte den Verdacht, daß alle ungeraden Zahlen Primzahlen sind. Jedenfalls, so argumentiert er, kann 1 als Primzahl betrachtet werden. Dann kommen 3, 5 und 7, alle zweifellos Primzahlen. Dann kommt 9; ein peinlicher Fall, wir scheinen hier keine Primzahl zu haben. Aber 11 und 13 sind unbestreitbar Primzahlen. 'Auf die 9 zurückkommend', sagt er, 'schließe ich, daß 9 ein Fehler im Experiment sein muß.'"

Es liegt nur allzu sehr auf der Hand, daß Induktion zum Irrtum führen kann. Um so bemerkenswerter ist es, da die Irrtumswahrscheinlichkeiten so überwältigend erscheinen, daß Induktion manchmal zur Wahrheit führt.
[Mathematik-Folklore]

Die vollständige Induktion ist eine der 3 grundlegenden mathematischen Beweistechniken - neben 'direkt' und 'indirekt durch Widerspruch'. Um eine Beweistechnik als Mittel der korrekten logischen Argumentation zu akzeptieren, muß man diese Technik verstanden haben. Das Prinzip der vollständigen Induktion ist immerhin schon so komplex, daß es Gegenstand von Witzen sein kann.

Themenüberblick

  1. Wer hat die vollständige Induktion erfunden?
  2. Ist Induktion nur etwas für Folgen und Reihen?
  3. Wie funktioniert die vollständige Induktion?
    1. Zusammenfassung Induktionsverfahren
  4. Kann man sich auf die vollständige Induktion verlassen?.
  5. Kann man denn wirklich den Induktionsschluß unendlich oft anwenden?.
  6. Was ist schwer an der vollständigen Induktion?
  7. Kann man denn Induktion immer anwenden?
    1. Peano-Axiome
  8. Induktion kann man nicht anwenden, wenn ...
  9. Anwendungen der vollständigen Induktion
    1. Geometrie
    2. Mengenlehre
    3. Binomialkoeffizienten
    4. Geometrisches und Arithmetisches Mittel
    5. Summenformeln
    6. Abschätzungen
    7. Teilbarkeit
    8. Zahlentheorie
    9. Rekursiv definierte Folgen
    10. Eindeutigkeitsbeweis
    11. Differentialrechnung
  10. Schluß
    Fraktal
  1. Wer hat die vollständige Induktion erfunden?

    Induktives Denken, also das Schließen vom Besonderen auf das Allgemeine, gibt es solange Menschen denken. Die Frage ist also, seit wann die vollständige Induktion methodisch so ausformuliert und handhabbar war, daß man von einer erlaubten und zuverlässigen Beweistechnik sprechen kann. Philosophen, Wissenschaftler, Mathematiker haben schon im Altertum induktive Beweise gegeben. Die strenge mathematische Induktion ist das nicht in jedem Fall gewesen und es gab jahrhundertelange Dispute.
    Ein Überblick dazu findet sich bei: Lexikon der Philosophie bei phillex.de.

    In einem Beitrag der TU Freiberg steht

    Der erste Mathematiker, der einen formalen Beweis durch vollständige Induktion angab, war der italienische Geistliche Franciscus Maurolicus (16.9.1494 - 21./22.7.1575). Er war Abt von Messina und wurde als größter Geometer des 16. Jahrhunderts angesehen. In seinem 1575 veröffentlichten Buch Arithmetik benutzte Maurolicus die vollständige Induktion unter anderem dazu, für jede positive ganze Zahl n die Gültigkeit von

    1 + 3 + 5 + ... + (2n-1)=n*n

    zu beweisen. Die Induktionsbeweise von Maurolicus waren in einem knappen Stil geschrieben, dem man nur schwer folgen kann. Eine bessere Darstellung dieser Methode wurde von dem französischen Mathematiker Blaise Pascal (1623 - 1662) angegeben. In seinem 1662 erschienen Buch Traite du Triangle Arithmetique bewies er eine Formel über die Summe von Binomialkoeffizienten mittels vollständiger Induktion. Er benutzte diese Formel dann um das heute nach ihm benannte Pascalsche Dreieck zu entwickeln.

    Obwohl die Methode der vollständigen Induktion also bereits 1575 bekannt war, wurde der Name dafür erst 1838 erstmalig gebraucht. In jenem Jahr veröffentlichte Augustus de Morgan (1806 - 1871), einer der Begründer der Mengenlehre, den Artikel Induction (Mathematics) in der Londoner Zeitschrift "Penny Cyclopedia". Am Ende dieses Artikels benutzte er den Namen für die vollständige Induktion erstmals im heute üblichen Sinn. Jedoch fand diese Bezeichnung erst in unserem Jahrhundert ihre weite Verbreitung.
    [Zitat aus Vollständige Induktion von Prof. Dr. rer. nat. Udo Hebisch]

    Übrigens das Gegenteil von Induktion ist die Deduktion, bei der man vom Allgemeinen auf das Einzelne schließt. Beispiel: Alle Menschen haben einen Kopf. Peter ist ein Mensch. Folgerung: Peter hat einen Kopf. Aber darum soll es weiter nicht gehen.
  2. Fraktal

  3. Ist Induktion nur etwas für Folgen und Reihen?

    Nein, aber bei diesen Schulthemen, die üblicherweise in der 11. Klasse behandelt werden, wird die vollständige Induktion eingeführt. Bis dahin bestand keine Notwendigkeit dazu. Anwendung der vollständigen Induktion findet man in allen mathematischen Gebieten, von Mengenlehre bis Geometrie, von Diffenrentialrechnung bis Zahlentheorie. Sogar der Beweis des großen Fermatschen Satzes (Wiles) verwendet die vollständige Induktion (neben vielen anderen Argumenten).

    Ich werde unten vielfältige Beispiele für Beweise mit vollständiger Induktion geben.

  4. Wie funktioniert die vollständige Induktion?

  5. Für eine gegebene Behauptung zeigt man, daß die Behauptung für ein oder einige kleine n gilt (Induktionsanfang). Ausgehend von dieser wahren Voraussetzung zeigt man, daß die Behauptung für das nächste n (also n+1) sich aus der Gültigkeit der Behauptung für ein oder alle kleineren Zahlen n herleiten läßt.
    Die hierbei verwendete Schlußweise ist so vorzunehmen, daß sie "übertragbar" oder "wiederverwendbar" ist.
    Wenn eine Behauptung z.B. für n=1 ist richtig ist, dann hat man damit den Induktionsanfang. Der Induktionsanfang ist der feste Punkt, an den alles folgende anknüpft. Ohne Induktionsanfang ist auch ein noch so schöner Induktionsschluß nichts wert. Man kann aus einer Aussageform A vielleicht die Aussageform B folgern. Aber um zu wissen, ob B deswegen wahr ist oder nicht, muß man wissen, ob A wahr ist oder nicht.
    Das ist nicht schwer zu verstehen. Nehmen wir die Aussagen A: [5 ist durch 2 teilbar] und B: [7 ist durch 2 teilbar]. Natürlich ist 5 nicht durch 2 teilbar, aber aus der Aussage [5 ist durch 2 teilbar] folgert man logisch korrekt, daß auch 7 durch 2 teilbar ist. Die Schlußweise ist auf jeden Fall korrekt, nur die Voraussetzung war eben nicht gegeben.

    Wenn also der Induktionsanfang abgesichert ist, dann weiß man, daß die Behauptung für alle n £ einem bestimmten n0 gilt (das ist oft nur eine einzige natürliche Zahl, meistens die 1).
    Diese Formulierung mit n0 nennt man dann die Induktionsvoraussetzung.

    Nun kommt der Induktionsschritt. Formal lautet der:
    Aus der Gültigkeit der Behauptung für n£n0 folgt die Gültigkeit der Behauptung für n£n0+1 (die Induktionsbehauptung).

    Wenn man das zeigen kann, was hat man dann davon?
    Wenn die Behauptung für n0=1 gilt, dann gilt sie auch für n0=2.
    Wenn die Behauptung für n0=2 gilt, dann gilt sie auch für n0=3.
    Wenn die Behauptung für n0=3 gilt, dann gilt sie auch für n0=4.
    usw.
    Den Induktionsschritt von n->n+1 kann man beliebig oft (in Gedanken) anwenden. Die Schlußweise ist immer die gleiche.
    Folglich gilt die Behauptung für alle nÎN.

    Ich habe jetzt zur Verdeutlichung immer n0 geschrieben, weil man die Induktionsvoraussetzung nur für eine oder einige natürliche Zahlen geprüft hat und voraussetzen darf. Mehr war im Induktionsanfang ja nicht nachgewiesen worden. In der Praxis schreibt man eigentlich immer n statt n0 und weiß dennoch, was gemeint ist.

    Zusammenfassung Induktionsverfahren

    Die Folge von Induktionsanfang, Induktionsvoraussetzung, Induktionsbehauptung und Induktionsschritt nennt man vollständige Induktion.
    1. Prüfe den Induktionsanfang: A(0).
    2. Formuliere die Induktionsvoraussetzung: A(n).
    3. Formuliere die Induktionsbehauptung: A(n+1).
    4. Beweise den Induktionsschritt: A(n) Þ A(n+1).

    Vielleicht sollte ich zur Klarheit noch die Begriffe Aussage und Aussageform erklären. Eine Aussage ist eine überprüfbare Eigenschaft irgendwelcher konkreten Dinge. Beispiele: [Menschen haben einen Kopf] oder [Primzahlen sind durch 2 teilbar]. Eine Aussage kann wahr oder falsch sein, aber sie ist auf jeden Fall überprüfbar bzw. entscheidbar. Eine Aussageform dagegen ist eine Aussage, die eine Variable enthält, z.B. [n ist durch 2 teilbar]. Bei der vollständigen Induktion ist A(0) eine Aussage und A(n) eine Aussageform. Auch [A(n)ÞA(n+1)] ist eine Aussageform. Dagegen ist das, was man eigentlich mit vollständiger Induktion beweisen will, nämlich [Für alle natürlichen Zahlen n gilt A(n)] eine Aussage und keine Aussageform, denn dies ist eine Aussage über alle natürlichen Zahlen, deren Wahrheitsgehalt nicht von der Wahl eines bestimmten n abhängt. Die Aussage ist nämlich falsch, wenn sie für eine einzige natürliche Zahl n0 nicht gilt, egal welches. Ein Beispiel: Die Aussage [alle natürlichen Zahlen sind kleiner als 100] ist falsch. Die Aussageform [die natürliche Zahl n ist kleiner als 100] dagegen ist wahr für n<100 und falsch für n>99.

    Fraktal

  6. Kann man sich auf die vollständige Induktion verlassen?

    Ja, wenn man die Beweistechnik richtig anwendet. Man darf nicht schludern. Wenn man mit vermeintlich vollständiger Induktion glaubt offensichtlichen Unsinn beweisen zu können, dann hat man einen Fehler gemacht. Solche Fehler kommen vor, berechtigen aber nicht zu Zweifeln an der Methode. Ebensowenig zweifelt man an den Regeln für Termumformungen, nur weil man sich beim Ausklammern oder Zusammenfassen oder den Minuszeichen vertun kann.
    Gelegentlich sind falsche "Induktionsschlüsse" gerade dazu geeignet, die letzten Unsicherheiten bzgl. der Beherrschung der Methode aufzudecken und zu beseitigen.

    Falsches Beispiel 1:

    Socken im Koffer
    [Gefunden bei mathekiste.de]

    Falsches Beispiel 2:

    Behauptung: Wenn sich unter n Tieren ein Elefant befindet, dann sind alle diese Tiere Elefanten.
    Beweis durch vollständige Induktion:
    Induktionsanfang: n=1 : Wenn von einem Tier eines ein Elefant ist, dann sind alle diese Tiere Elefanten.
    Induktionsvorausetzung: Die Behauptung sei richtig für alle natürlichen Zahlen kleiner oder gleich n.
    Induktionsschluß: Sei unter n+1 Tieren eines ein Elefant. Wir stellen die Tiere so in eine Reihe, daß sich dieser Elefant unter den ersten n Tieren befindet. Nach Induktionsannahme sind dann alle diese ersten n Tiere Elefanten. Damit befindet sich aber auch unter den letzten n Tieren ein Elefant, womit diese auch alle Elefanten sein müssen. Also sind alle n+1 Tiere Elefanten. ?????

    Was daran falsch ist?
    Im Fall n+1=2 kann man den Elefanten zwar so stellen, daß er bei den ersten n=1 Tieren steht. Folglich sind alle Tiere unter den ersten n=1 Tieren Elefanten. Aber deshalb befinden sich unter den "letzten" n Tieren nicht notwendig Elefanten.

    Der Induktionsschluß funktioniert nur für n>1, denn nur dann können aus einem Elefanten zwei (oder mehr) werden und ist damit auch ein Elefant unter den letzten n Tieren.
    Die Induktionsvoraussetzung war aber gezeigt für n=1.
    Man müßte also zunächst zeigen, daß von zwei Tieren, von denen eines ein Elefant ist, auch das andere ein Elefant ist. Aber das wird schwer.
    Der eigentliche Fehler des "Beweises" liegt darin, daß (n+1)/2 nicht immer größer als 1 ist. Wenn wir uns n+1 Dinge in einer Reihe vorstellen, dann sehen wir vor unserem inneren Auge eine lange Reihe, mit 10 oder 20 oder 1000 Dingen (Tieren). Aber eine Reihe von Tieren kann auch aus 2 Tieren bestehen. Dafür gilt der vermeintliche Induktionsschluß nicht.

  7. Fraktal

  8. Kann man denn wirklich den Induktionsschluß unendlich oft anwenden?

    Das dauert doch unendlich lange, und noch niemand hat das jemals bis zum Ende durchführen können.
    Guter Einwand. Man muß das auch nicht tun. Die Formulierung "für alle n" scheint das nahezulegen, aber es nicht so. Wenn eine Behauptung durch vollständige Induktion bewiesen ist, dann zeigt der Beweis, wie aus vorausgesetztem A(n) die Gültigkeit für A(n+1), also der gleichen Aussageform für die nächste natürliche Zahl, folgt. In die Behauptung, die wir gerne für alle n als richtig einsehen möchten, wird niemals ¥ eingesetzt. Wir verwenden die Behauptung immer für ein festes aber beliebiges n. Wenn wir eine Summenformel åk=1n k = n*(n+1)/2 verwenden, dann z.B. für n=1000. Den Induktionsschluß aus dem Beweis der Summenformel kann man theoretisch 1000-mal durchführen, Wenn aber die Summe der Zahlen bis n=1.000.000 gefragt ist, dann machen wir den Induktionsschluß 1.000.000-mal. Das dauerte zwar lange, ist aber in endlicher Zeit zu schaffen (und wenn nicht von einem Menschen, dann von 100 Menschen oder mit Computern).
    Tatsächlich wird niemand jemals den Induktionsschritt eine Million mal anwenden. Der Induktionsschluß zeigt ja, wie das jeweils zu machen ist. Und das reicht. Die Zeit können wir uns sparen.
    Aber es ging ja hier auch um die Frage nach der unendlichen Wiederholbarkeit des Induktionsschlusses. Antwort: Der Induktionsschluß muß nicht unendlich oft wiederholt werden. Die durch vollständige Induktion gewonnenen Formeln und Ergebnisse gelten für feste aber beliebige natürliche Zahlen n.
  9. Was ist schwer an der vollständigen Induktion?

    Die vollständige Induktion ist ein konstruktives Beweisverfahren. Der Induktionsschritt zeigt wie man im allgemeinen die Gültigkeit einer Behauptung aus einfachen Anfängen heraus auf alle möglichen Objekte (Zahlen) ausweitet.
    Konstruktive Beweise erfordern konstruktive Argumente. Solche muß man erst einmal finden. Konstruktiv kann ein Argument ja nur sein, wenn es in Bezug auf die Aufgabenstellung wirklich etwas aussagt. Im oben angeführten Sockenbeispiel war das Argument [die Erfahrung sagt, daß immer noch ein Paar Socken mehr in den Koffer paßt] nicht konstruktiv. Ein konstruktives Argument sagt genau wo, die Lücke für das weitere Paar Socken sein wird.
    Man kann induktive Beweise nur führen, wenn man die durch die Ausgangssituation gegebenen Fakten gut analysiert und eine Idee entwickelt, die dem Problem genau angemessen ist.

    Die Durchführung des Induktionsschritts erfordert zudem handwerkliche mathematische Fähigkeiten. Gerade bei Induktionsbeweisen muß man die Regeln der Termumformungen und die Handhabung von Summenzeichen und Variablenindizes beherrschen. Nur dann kann man die richtige Idee auch wirklich verifizieren.

  10. Fraktal

  11. Kann man denn Induktion immer anwenden?

    Was heißt "immer"? Man kann Induktion nur anwenden, wenn die Behauptung irgendwelche Objekte (Zahlen, Geraden, Teilmengen, ...) behandelt und wenn zwischen den Objekten und den natürlichen Zahlen eine Bijektion (eine eineindeutige Abbildung) möglich ist.
    Ich werde später Beispiele für Anwendung der vollst. Induktion auf andere Objektmengen als die natürliche Zahlen geben. Um die vollst. Induktion anwenden zu können, genügt, daß die Objektmenge die Peano-Axiome erfüllt. Siehe: Die Axiome der natürlichen Zahlen nach Peano [gefunden bei mathefuzzy]
    Weil die genannte Seite aber seit 3 Jahren nicht mehr aktualisiert worden ist und sich schon etwas in Auflösung zu befinden scheint, möchte ich wesentliche Abschnitte im Zitat wiedergeben:
    Die natürlichen Zahlen standen ganz am Anfang unseres Aufbaus des Zahlensystems. Wir haben so getan, als seien sie unproblematisch und jedermann vom Abzählen und vom Anordnen her wohlbekannt. Das war auch in der geschichtlichen Entwicklung der Mathematik so. Während die irrationalen und die negativen Zahlen den Gegenstand von langwierigen Auseinandersetzungen bildeten, kümmerte man sich um die natürlichen Zahlen nur wenig. Gegen Ende des 19. Jahrhundert änderte sich dies. Den Mathematikern war es gelungen alle anderen Zahlenarten auf die natürlichen zurückzuführen. Damit stellte sich die Frage "Was ist eigentlich eine natürliche Zahl?" Eine Antwort hierauf gab der italienische Mathematiker Giuseppe Peano (1858-1932) im Jahre 1889. Peano nannte fünf Eigenschaften, die die Menge der natürlichen Zahlen N kennzeichnen:

    Die Axiome der natürlichen Zahlen nach Peano

    1. 1 ist eine natürliche Zahl.
    2. Zu jeder Zahl n gibt es eine eindeutig bestimmte natürliche Zahl n*, genannt der Nachfolger von n.
    3. 1 ist nicht der Nachfolger irgendeiner natürlichen Zahl.
    4. Zwei natürliche Zahlen n und m, deren Nachfolger gleich sind (d.h. m* = n*), sind selbst gleich (d.h. m = n).
    5. Es sei T eine Teilmenge der natürlichen Zahlen mit folgenden Eigenschaften:
      1. 1 gehört zu T;
      2. gehört n zu T, dann ist auch der Nachfolger n* von n ein Element von T.
      Dann stimmt T mit N überein.

    Man nennt diese Eingenschaften heute die Peano- Axiome. Mit dem Begriff "Axiom" bezeichnet man Annahmen, die man als wahr voraussetzt . Für die Zwecke der Mathematik genügt es, die Menge der natürlichen Zahlen als dasjenige Gebilde zu betrachten, das diese fünf Eigenschaften besitzt.
    Das letzte, sehr komplex wirkende Axiom wird "Axiom der vollständigen Induktion" genannt.
  12. Fraktal

  13. Induktion kann man nicht anwenden, wenn ...

    Man kann also Aussagen über reelle Zahlen niemals mit vollständiger Induktion beweisen, denn es gibt keine Bijektion zwischen N und R (siehe Cantors Diagonalbeweis).

    Oftmals ist man auch versucht, die Induktion immer für möglich zu halten, wenn nur ein n in der Behauptung vorkommt. Wenn man etwas beweisen will oder muß, dann ist die Suche nach der richtigen Beweismethode erforderlich. Die Möglichkeit der Verwendung der vollst. Induktion gehört dazu. Man muß aber auch lernen, wann die vollständige Induktion nicht geeignet ist. Beispiel: Die Aussage: [Die Folge a(n) = 1/n ist immer positiv.] kann man nicht mit vollständiger Induktion beweisen. Wie sollte man aus A(n): [1/n > 0] denn folgern, daß A(n+1): [1/(n+1) > 0] ist? Gut, beide Aussageformen sind wahr, aber man kann A(n+1) nicht aus A(n) folgern. Man muß hier andere Argumente verwenden. Nicht aus jeder wahren Voraussetzung kann man jede andere wahre Behauptung folgern.

  14. Anwendungen der vollständigen Induktion

    Für mich stammen die schönsten Beispiele für vollständige Induktionen aus dem Bereich der Geometrie. Man hat weniger mit mathematischem Handwerkszeug zu kämpfen und kann sich auf die Suche nach der (konstruktiven) Idee begeben, ohne schon an der sonst oft formalen Formulierung der Behauptung zu scheitern.

    1. Geometrie

      1. Aufgabe: Zeige, daß die Zahl d(n) der Diagonalen in einem ebenen, konvexen n-Eck durch die Formel
        d(n) = n/2 * (n-3)
        berechnet werden kann! Für welche n gilt die Formel?

        Lösung:
        Idee: vollst. Induktion über die Anzahl der Ecken.
        Induktionsanfang für ein Dreieck. Ein Dreieck hat keine Diagonalen, also d(3) = 0 = 3/2 * (3 - 3). Für n=3 ist die Behauptung richtig.
        Induktionsschritt: Stelle Dir ein konvexes n-Eck vor (z.B. ein Fünfeck). In dieses zeichne eine Diagonale von einem beliebigen Eckpunkt zu einem "übernächsten" Eckpunkt, also so, daß ein Dreieck und ein (n-1)-Eck entsteht.

        Induktionschritt
        Konvexes, ebenes n-Eck, durch eine Diagonale zerlegt in ein (n-1)-Eck und ein 3-Eck

        Das Dreieck hat keine und das (n-1)-Eck hat d(n-1) Diagonalen (Induktionsvoraussetzung).
        Außerdem muß man noch die Diagonalen von der Ecke des Dreiecks, die nicht eine Ecke des (n-1)-Ecks ist, zu allen Ecken des (n-1)-Ecks, die nicht Eckpunkt des Dreiecks sind, zählen - und nicht zu vergessen die eine Diagonale, mit der das Dreieck abgeteilt wurde.
        Folgt: d(n) = d(n-1) + (n-3) + 1
          = (n-1)/2 * ((n-1)-3) + (n-3) + 1
          = (n-1)*(n-4)/2 + n -2
          = (n2-5n+4)/2 + n -2
          = (n2-3n)/2
          = (n * (n-3)) / 2
        Fertig.

        Einige Bemerkungen:

        • Der Induktionsanfang wurde für n=3 gemacht. Für kleinere n kann man den Induktionsschluß nicht durchführen, das geht erst ab einem (3+1)-Eck. Ein Polygon mit weniger als 4 Ecken erlaubt nicht das Einzeichnen einer Diagonale von einer Ecke zu einer "übernächsten" Ecke. Im Dreieck ist ja jede andere Ecke benachbart.
        • Als Induktionsschritt wurde [A(n-1)ÞA(n)] gezeigt. Das ist erlaubt, man muß aber angeben, für welche n dieser Schritt gilt. Der Induktionsschritt gilt für alle n³4. Es ist dasselbe, ob man für n³3 [A(n)ÞA(n+1)] oder für n³4 eben [A(n-1)ÞA(n)] zeigt. Warum der Induktionsschritt nicht von n auf n+1 vorgeführt wurde ...? Ach, das sind die kleinen Unwichtigkeiten, mit denen die Anfänger verwirrt werden.
      2. Behauptung: Durch n Geraden (in allg. Lage) wird die Ebene in (n2+n+2)/2 Teile zerlegt. (Anleitung: jede weitere Gerade zerlegt eine ganz best. Anzahl der schon vorhandenen Gebiete in 2 Teile.)

        Zunächst ist festzustellen, daß ein "höchstens" fehlt. Durch n Geraden wird die Ebene höchstens in ... Teile zerlegt. Die Geraden könnten ja parallel oder identisch sein.

        Induktionsanfang: n=1. Eine Gerade teilt die Ebene in 2 Gebiete und (12+1+2)/2 ist gleich 2.

        Induktionschritt
        Die (n+1)-te Gerade teilt maximal n+1 Gebiete

        Wie kann man den Induktionsschluß machen?
        Die (n+1)-te Gerade kann höchstens n Geraden schneiden. Immer wenn die neue Gerade eine vorhandene Gerade schneidet, dann tritt sie in ein neues Gebiet der Ebene ein. Die Anzahl der Gebiete, die von der neuen Geraden geteilt werden ist (höchstens) n+1, denn das erste Gebiet wird ja schon geteilt, bevor die neue Gerade die erste vorhandene Gerade schneidet. Und "höchstens" deshalb, weil ja vorkommen kann, daß zwei (oder mehr) Geraden zugleich geschnitten werden.
        Die Anzahl der neuen Gebiete ist also für n+1 höchstens = (n2 + n + 2) / 2 + ( n + 1 ).
        Man kann dann zeigen, daß dies gleich ((n+1)2 + (n+1) + 2) / 2 ist.

      3. Anzahl de Rechtecke in einem quadratischen Gitter. Induktion über die Summe der Zeilen und Spalten.
        Rechtecke in quadratischem Gitter
      4. Aufgabe: In der Ebene seien n Punkte A1,A2,...,An gegeben. Der Abstand zwischen je zwei von ihnen sei nicht größer als die Längeneinheit e. Man beweise, daß alle diese Punkte in einem Kreis mit dem Radius e / Ö3 enthalten sind.

        Lösung:
        [Vorbemerkung: Weil es in HTML einfacher ist, schreibe ich oft w(3) statt Ö3.]
        Die Länge e/Ö3 entspricht genau dem Umkreisradius eines gleichseitigen Dreiecks mit Seitenlänge e.
        Den Induktionsanfang macht man am besten mit n=3 Punkten. Die Behauptung gilt zwar auch für n<3, aber die Begründungen liegen da anders. Bei nur zwei Punkten reicht ja ein Kreis mit Radius e/2, und bei einem Punkt reicht jeder beliebige Radius.

        Also für n=3 gilt die Behauptung, weil die drei Punkte innerhalb eines gleichseitigen Dreiecks mit Seitenlänge e liegen.
        Induktionsvoraussetzung:
        n Punkte, von denen je zwei höchstens den Abstand e haben, liegen in einem Kreis mit Radius e/w(3).

        Induktionsschritt: seien n+1 Punkte gegeben, von denen je zwei höchstens den Abstand e haben.
        Sei P ein beliebiger Punkt.
        Wenn man P außer acht läßt, dann gibt es nach Induktionsvoraussetzung für die übrigen n Punkte einen Kreis mit Radius e/w(3), in dem die n Punkte liegen.
        Wenn P auch in diesem Kreis liegt, ist man schon fertig.
        Wenn P aber nicht in dem Kreis liegt, dann hat P also vom Mittelpunkt M des Kreises einen Abstand > e/w(3).

        Induktionschritt
        Der (n+1)-te Punkt P liegt nicht in dem Kreis mit Radius e/w(3), der die ersten n Punkte überdeckt. Weil P mit jedem der n Punkte höchstens den Abstand e hat, ist es möglich den Kreis zu verschieben, so daß alle n+1 Punkte in einem Kreis mit Rasius e/w(3) liegen (roter Kreis).

        Sei g die Verbindungsstrecke von P und M.
        Sei M' der Punkt auf g, der von P genau den Abstand e/w(3) hat. Nun schlage einen Kreis mit Radius e/w(3) um M'. Entweder liegen in diesem Kreis alle n+1 Punkte, dann ist man fertig. Oder es müßte einen Punkt P' geben, der nicht in diesem Kreis um M' liegt.

        Für diesen (vermeinlichen) zweiten Fall kann man aber einen Widerspruch zeigen.
        Wir hätten dann also einen Punkt P, der von M einen Abstand > e/w(3) hat und einen Punkt P', der von M' einen Abstand >e/w(3) hat.
        Nun zeichne einen Kreis mit Radius e/w(3) um P und einen ebensolchen um P'.
        Die beiden Kreise schneiden sich nicht, denn P und P' liegen ja nach Konstruktion nicht beide in einem der Kreis mit Radius e/w(3) um M bzw. M'. Und - auch wichtig - M' war ein Punkt auf der direkten Verbindungsstrecke von M und P, der echt näher an P lag als M (sonst hätte man nicht M' konstruieren müssen).
        Also ist der Abstand von P und P' > 2 * e/w(3) > e. Ein Widerspruch.
        D.h. die Annahme, daß P nicht schon im Kreis um M liegt, ist falsch gewesen.

        Was sagt uns der Beweis: Es kann sein, daß der Mittelpunkt für einen Kreises, der n Punkte einschließt, nicht zugleich der Mittelpunkt für einen Kreis ist, der n+1 Punkte einschließt.
        Evtl. muß man den Mittelpunkt noch verschieben. Wie man den richtigen Mittelpunkt M' findet, sagt der Beweis.
        Das so konstruierte M' ist wirklich der gesuchte Kreismittelpunkt, denn unter Annahme des Gegenteils erhält man einen Widerspruch.

        Der Beweis erscheint etwas ungenau, weil hier mit einem Abstand |PP'|>2e/w(3) argumentiert wird. Das ist zwar hinreichend für den Widerspruch, aber weniger wäre hier auch schon genug, nämlich |PP'|>e. Das liegt aber an einer Schwäche der Behauptung. Nehmen wir den Fall n=3 und Punkte die ein gleichseitiges Dreieck mit Seitenlänge e bilden.
        Dann liegen also alle 3 Punkte auf der Peripherie eines Kreises mit
        Radius e/w(3).
        Und nun kommt der Schwachpunkt der Behauptung: Dieser Kreis enthält auch Punkte, die zu mindestens einem der Punkte Abstand =2e/w(3) haben. Wenn nämlich P einer der 3 Punkte ist und Q ist der Punkt "genau gegenüber" auf der Peripherie, dann ist der Abstand 2*Radius =2e/w(3).
        Man kann die Behauptung also nicht umkehren. Wenn n Punkte in einem Kreis mit Radius e/w(3) liegen, dann ist nicht notwendig der Abstand von je zwei Punkten £e.

    2. Mengenlehre

      1. Behauptung: Sei M eine beliebige Menge und m=|M| die Anzahl der Elemente von M. Zeige, daß |P(M)|=2m.

        Lösung: die Potenzmenge P(M) ist die Menge aller Teilmengen von M. Die Frage ist also, wieviele verschiedene Teilmengen man aus m Elementen bilden kann. Um das zu zählen gibt es verschiedene Möglichkeiten, ja nachdem, was man verwenden darf. Was man immer anwenden kann, ist vollständuge Induktion.
        A) Wenn M={}, also |M|=0, dann ist P(M)={{}}, denn nur die leere Menge ist Teilmenge der leeren Menge. Also |P(M)|=1=20.
        B) Sei nun |M|=n+1. Sei x ein bestimmtes Element aus M. Bilden wir nun alle Teilmengen.

        Wir können die Teilmengen aufteilen in
        a) die Teilmengen, die x nicht enthalten,
        b) die Teilmengen, die x enthalten.

        Nach Induktionsvorausetzung wissen wir, das die Anzahl der Teilmengen bei a) = 2n ist, denn es handelt sich ja um alle Teilmengen einer Menge mit n Elementen.
        In allen Teilmengen aus b) können wir das Element x entfernen. Dann ist die Anzahl dieser Mengen also auch = 2n, denn es handelt sich auch hier um alle Teilmengen einer Menge mit n Elementen.
        Addiere nun die Anzahlen für a) und b)
        2n + 2n = 2n+1.
        Fertig.

    3. Fraktal

    4. Binomialkoeffizienten
      1. Beweise Sn k=0 (a+kk) = (a+n+1n)

        Beweis mit Induktion:
        n=0: (a+00) = (a+0+10). Stimmt, denn beide Binomialkoeffizienten sind gleich 1.
        Induktionsschritt:
        Was ist zu zeigen:
        Unter der Voraussetzung, daß die Beziehung für n schon bewiesen ist, muß man zeigen:
        Sn+1 k=0 (a+kk) = (a+(n+1)+1n+1)
        Also immer da wo n stand, muß jetzt n+1 stehen.

        Zum Beweis:
        Sn+1 k=0 (a+kk)
        = Sn k=0 (a+kk) + (a+n+1n+1)
        = (a+n+1n) + (a+n+1n+1)
        = (a+(n+1)+1n+1)
        Fertig.
        Dabei habe ich die Summe mit n+1 Summanden erstmal aufgeteilt in n Summanden und einen. Für die Summe bis n kann man die Induktionsvoraussetzung anwenden.
        Schließlich gibt es noch eine Beziehung zwischen Binomialkoeffizienten, die es sich zu merken lohnt:
        (nk-1)+(nk) = (n+1k)
        [Diese Formel kann man auch wieder mit vollst. Induktion beweisen.]
        Damit habe ich dann zusammengefaßt und erhalte das gesuchte Ergebnis.
      2. Beweise: Es sei x Î R. Man zeige für alle n Element N mit 0 gilt:

        (1+x)n=Sn v=0(nv) * xv

        Auch das geht mit Induktion.
        Für n=0 steht da (1+x)0 = (00)*x0 und das ist richig.
        Für n=1: 1+x = (10)*x0 + (11)*x1 auch richtig.
        Nun der Induktionsschritt:
        (1+x)n+1 = (1+x)n * (1+x)
        = (1+x) * Sn i=0 (ni)*xi
        = 1* Sn i=0 (ni)*xi + x* Sn i=0 (ni)*xi
        = Sn i=0 (ni)*xi + Sn i=0 (ni)*xi+1
        jetzt verschiebe ich den Index in der zweiten Summe.
        = Sn i=0 (ni)*xi + Sn+1 i=1 (ni-1)*xi
        In den beiden Summen kommen die Potenzen x1 bis xn vor. Aber x0 ist nur in der ersten Summe und xn+1 nur in der zweiten Summe. Ich zerlege die Summen dementsprechend.
        = 1 + Sn i=1 (ni)*xi + Sn i=1 (ni-1)*xi + xn+1
        Und dann kann ich die beiden Summen zusameenfassen:
        = 1 + Sn i=1 [(ni) + (ni-1) ]*xi + xn+1
        Nun gilt für die Binomialkoeffizienten die folgende Beziehung: (ni) + (ni-1) = (n+1i)
        Das eingesetzt ergibt:
        = 1 + Sn i=1 (n+1i)*xi + xn+1
        und dann
        = Sn+1 i=0 (n+1i)*xi

      3. Beweis des Binomischen Lehrsatzes
        Beweise:
        (a+b)n = Sn i=0 (ni) aibn-i
        Vollständige Induktion.
        n=0 => 1 = 1 stimmt!
        Induktionsschritt:
        (a+b)n+1 = [ Sn i=0 (ni) aibn-i ]*(a+b)
        unter Verwendung der Induktionsvoraussetung (für n).
        = a*Sn i=0 (ni) aibn-i + b* Sn i=0 (ni) aibn-i
        = Sn i=0 (ni) ai+1bn-i + Sn i=0 (ni) aibn-i+1
        = an+1 + Sn-1 i=0 n!/(i!*(n-i)!) ai+1bn-i + bn+1 + Sn i=1 n!/(i!*(n-i)!) aibn-i+1

        Was passiert denn hier eigentlich?
        Um besser durchzublicken, schreibe ich die Formeln für n=3:
        (a+b)3 = [ a3 + 3a2b1 + 3a1b2 + b3]*(a+b)
        = a *[ a3 + 3a2b1 + 3a1b2 + b3] + b*[ a3 + 3a3b1 + 3a1b2 + b3]
        = a4 + 3a3b1 + 3a2b2 + a1b3 + a3a1 + 3a2b2 + 3a1b3 + b4
        Die gemischten Potenzen kommen je zweimal vor, die Potenzen "hoch 4" je einmal. Ich ordne um:
        = a4 + (3+1)*a3b1 + (3+3)*a2b2 + (1+3)*a1b3 + b4
        Aha, der Koeffizient vor a3b1 ist die Summe von zwei anderen Binomialkoeffizienten. Und zwar (nk-1)+(nk) und das ist (n+1k).
        Und da haben wir die Formel für n=4.

        Entschuldigung, daß ich es dabei belasse. Bei der vorigen Aufgabe mit (1+x)n war ich noch ausführlich. Hier ist es doch genau dasselbe.

      Fraktal

    5. Geometrisches und Arithmetisches Mittel
      1. Wie kann man denn am besten beweisen, daß das geometrische Mittel kleiner gleich dem arithmetischen Mittel ist? Induktion habe ich schon ausprobiert, aber... Seien a1, ... ,an positive reelle Zahlen.
        Dann gilt:
        geometrisches Mittel <= arithmetisches Mittel

        Wir beweisen zuerst folgenden

        Hilfssatz: Gilt für reelle Zahlen b1, ... ,bn:
        Pk=1n bk = 1, so ist Sk=1n bk >= n
        Gleichheit gilt genau dann, wenn b1=b2=...=bn.
        Beweis des Hilfssatzes mit vollständiger Induktion über n.
        Für n=1 gilt die Behauptung.
        Betrachte nun die Zahlen b1,...,bn,bn+1.
        Wenn alle bi gleich sind und Pk=1n bk = 1, dann folgt, daß alle bi=1,
        und es ist klar, daß Sk=1n bk = n+1.
        Falls aber nicht alle bi=1 sind,
        dann ist o.B.d.A. b1 < 1 < b2 weil Pk=1n bk = 1.
        Aus b1 < 1 < b2 folgt, daß (1 - b1)*(b2 - 1) > 0.
        Ausmultipliziert ist das: b1 + b2 > 1 + b1*b2.

        Aus der Induktionsvoraussetzung folgt für die n Zahlen

        b1*b2, b3, ... ,bn, bn+1:

        b1*b2 + Sk=3n+1 bk >= n.

        Insgesamt erhält man:
        Induktionsschluß.
        qed.

        Zurück zum Beweis der Behauptung über geometrisches und arithmetisches Mittel
        Wenn a1 = a2 = ... = an, dann ist die Behauptung trivial, und die Ungleichung gilt mit Gleichheit.

        Nehmen wir also an, daß die ai nicht alle gleich sind.
        Sei G := n-te Wurzel aus Produkt a_i.
        Betrachte bi := ai / G.

        Nach Konstruktion ist Pk=1n bk = 1.
        Da nicht alle bi gleich sind, folgt aus dem Hilfssatz:
        Beweis
        QED.

      Fraktal

    6. Summenformeln
      1. Vollständige Induktion ist wie Treppenlaufen lernen. Erst einmal muß man wissen, daß man überhaupt auf die erste Stufe klettern kann. Dann muß man den Weg finden, wie man von einer Stufe auf die nächste kommt. Und dann kommt man ja von der ersten auf die zweite, von der zweiten auf die dritte, etc.
        Wenn die erste Stufe nicht klappt, dann haut natürlich das ganze nicht hin.

        Summenformel für Zahlen von 1 bis n.
        Behauptung: 1+2+3+...+n = n*(n+1)/2

        Beweis mit Vollständiger Induktion:
        1. Induktionsanfang: n=1. 1 = 1*(1+1)/2 = 1 Paßt.

        2. Induktionsvoraussetzung: Für alle n £ k gilt die Behauptung. Insbesondere also 1+2+...+k=k*(k+1)/2 ¬ Das nennen wir jetzt abgekürzt "(IV)".

        3. Induktionsschritt. Man betrachtet, ob jetzt aus der Induktionsvoraussetzung schon folgt, daß auch für n = k+1 die Behauptung gelten muß. Also:
        1+2+3+...+k+(k+1) = (1+2+3+4+...+k) + (k+1)
        Jetzt setzen wir für den ersten Teil (IV) ein:
        = k*(k+1)/2 + k+1 = (k2+k)/2 + (2k+2)/2 = (k2+3k+2)/2 =
        (Faktorisieren)
        =(k+1)(k+2)/2 = (k+1)*((k+1)+1)/2

        Genau das sollte ja nach Behauptung herauskommen. Die Behauptung ist also bewiesen, denn... für n=1 wissen wir was los ist. Daraus folgt n=2. Daraus für n=3, usw.
        [Der Text ist fast wörtlich einem Beitrag aus zahlreich.de entnommen. Ich finde den Vergleich mit der Treppe gut.]
      2. Beweise folgenden Satz: 1+4+9+....+n2 = n*(n+1)*(2n+1)/6
        Für n=1, ist Sn k=1 n2 = 1. ok.
        Nun Sn+1 k=1 n2 = Sn k=1 n2 + (n+1)2 = n * (n+1) * (2n+1)/6 + (n+1)2
        Um das zu zeigen, muß man mit Hilfe der Induktionsvoraussetzung die Terme der Induktionsbehauptung ausmultiplizieren und zusammenfassen, bis man das gewünschte Ergebnis (die Behauptung) vor sich stehen hat.

        Durch geschicktes Umformen kommt man schließlich auf (n+1) * (n+2) * (2(n+1)+1)/6.
        Oder man zeigt, daß gilt:
        n*(n+1)*(2n+1)/6 + (n+1)2 - (n+1) * (n+2) * (2(n+1)+1)/6 = 0
        Kräftig ausmultiplizieren, dann sieht man's.
        Bemerkung: Ich habe Sn+1 k=1 n2 zuerst so geschrieben: Sn k=1 n2 + (n+1)2.
        Das habe ich gemacht, weil ich dann auf die Summe bis n die Induktionsvoraussetzung (für kleinere Zahlen als n+1) anwenden kann. Denn für kleinere Zahlen als n+1 gilt die Behauptung, nämlich:
        Sn k=1 n2 = n*(n+1)*(2n+1)/6.

        Also ist
        Sn+1 k=1 n2 = n*(n+1)*(2n+1)/6 + (n+1)2.

        Was wir zum Nachweis der Behauptung gern sehen möchten, ist, daß
        Sn+1 k=1 n2 = (n+1)*((n+1)+1)*(2(n+1)+1)/6.

        Daß das eine gleich dem anderen ist, muß man jetzt durch ausmultiplizieren und zusammenfassen nachweisen. Mach das mal, und Du wirst sehen, daß die beiden Formeln gleich sind.
      3. Zeige Sn i=1 i3 = (Sn i=1 i )2

        Vollst. Induktion über n.
        n=1: 1=1 ok
        n+1: Es ist Sn+1 i=1 i3 = [ Sn i=1 i3 ] + (n+1)3
        Die Summe bis n kann nach Induktionsvoraussetung ersetzt werden:
        = [ Sn i=1 i ]2 + (n+1)3
        und das soll gleich [ Sn+1 i=1 i ]2 sein.
        Um das zu sehen, wende ich die Binomische Formel auf
        [ Sn+1 i=1 i ]2 = [ (Sn i=1 i ) + (n+1) ]2 an:
        = [ (Sn i=1 i ) ]2 + 2(n+1)*(Sn i=1 i ) + (n+1)2
        Für die Summenformel in der Mitte setze ich den seit Gauss bekannten Ausdruck ein:
        = [ (Sn i=1 i ) ]2 + 2(n+1)*1/2*n*(n+1) + (n+1)2
        = [ (Sn i=1 i ) ]2 + (n+1)*n*(n+1) + (n+1)2
        in den hinteren beiden Summanden klammere ich (n+1)2 aus:
        = [ (Sn i=1 i ) ]2 + (n+1)2* (n + 1)
        = [ (Sn i=1 i ) ]2 + (n+1)3
        Das war's.


      4. Zeige Sn k=0 k * (nk) = n*2n-1
        Beweis mit Induktion unter Verwendung der bekannten Beziehung: (n+1k) = (nk) + (nk-1).
        Induktionsvoraussetzung bitte selbst machen.
        Induktionsschritt:
        Sn+1 k=0 k * (n+1k)
        = Sn k=1 k * (n+1k) + (n+1)
        = Sn k=1 k * [(nk) + (nk-1)] +(n+1)
        = Sn k=1 k * (nk) + Sn k=1 k * (nk-1) + (n+1)
        = Sn k=0 k * (nk) + Sn-1 k=0 (k+1) * (nk) + n + 1
        = Sn k=0 k * (nk) + Sn-1 k=0 k * (nk) + Sn-1 k=0 (nk) + n + 1
        = Sn k=0 k * (nk) + Sn k=0 k * (nk) + Sn-1 k=0 (nk) + 1
        = Sn k=0 k * (nk) + Sn k=0 k * (nk) + Sn k=0 (nk)
        = n*2n-1 + n*2n-1 + 2n
        = 2*n*2n-1 + 2n
        = n*2n + 2n
        = (n+1)*2n
        Das war's schon.
        Die Arbeit besteht darin, die Summen ohne Fehler umzuformen und die Indizes zu transformieren.

      Fraktal

    7. Abschätzungen
      1. Man beweise: n/2 < S2n-1 i=1(1 / i) < n
        Induktion.
        Anfang: n=2. Stimmt.
        Dann S2n+1-1 i=1 1/i = S2n-1 i=1 1/i + S2n+1-1 i=2n 1/i
        Die erste Summe kann mit der Induktionsvoraussetzung abgeschätzt werden (nach oben bzw. nach unten). Um die zweite Summe nach oben abzuschätzen, schätze jeden Summanden gegen 1/22n ab. Insgesamt sind es 22n Summanden, also kann die zweite Summe gegen 1 abgeschätzt werden.
        Folglich ist
        = S2n-1 i=1 1/i + S2n+1-1 i=2n 1/i < n + 1. Das war der eine Teil.
        Und die Abschätzung nach unten: Schätze jeden Summanden der zweiten Summe gegen 1/2n+1 ab. Es sind 2n Summanden, also ist die zweite Summe größer als 1/2.
      2. Beweise, daß fur alle natürlichen Zahlen n gilt:
        (1/(1*3))+(1/(3*5))+...+(1/((2n-1)*(2n+1)))<1/2
        Das zeigt man nicht mit vollst. Induktion, wenigstens nicht direkt.
        Man hat ja nichts davon, zu wissen daß S(n)<1/2 ist, wenn man zeigen will, daß S(n+1)<1/2.
        [Ich verwende S(n) als Abkürzung für obige Summe.]

        Zur Lösung:
        Ich definiere a(n) = 1/[(2n-1)(2n+1)].
        Und S(n,m)=Sm i=n a(i), also die Summe über m-n+1 Folgenglieder, beginnend bei a(m).

        Beispiele
        S(1,1)=S1 i=1 a(i) = 1/3
        S(2,4)=S4 i=2 a(i) = 1/15 + 1/35 + 1/63 = 1/9
        S(5,12)=S12 i=5 a(i) = 1/27
        Die Anzahl der Summanden je Summe ist 1, 3, 9.
        Von vorne beginnend kann man jeweils die nächsten 3k Summanden addieren (k³0) und deren Summe ist gleich 1 / 3k+1.
        Also:
        Die ersten 30 Summanden addiert, ergibt 1/31.
        Die nächsten 31 Summanden addiert, ergibt 1/32.
        usw.

        Es läuft darauf hinaus, daß Sn i=1 a(i) <= Sx k=0 S(y,z) = Sx i=1 (1/3)i. Das ist eine geometrische Reihe mit q=1/3, der nur der i=0-Term fehlt. Mit 0-Term ist die Summe der geom. Reihe gleich (1-qn)/(1-q). Ohne 0-Term ist die Summe (1-qn)/(1-q) - 1. Mit q=1/3 kann man hier zeigen, daß das immer kleiner 1/2 ist.

        Was muß man nun noch tun?
        1. Eine Berechnungsvorschrift für x, y und z in Sn i=1 a(i) <= Sx k=0 S(y,z) angeben.
        2. Mit Induktion beweisen, daß diese Summen für die passenden x,y,z gleich 1/3? ist.

        Versuch mal, was Du auf diese Art erreichen kannst.
        Der Ansatz für den Beweis ist, daß man - wie ich schon geschrieben habe - die Summanden zu Gruppen zusammenfaßt (immer 3k Summanden, also erst 1, dann 3, dann 9 usw.) und für jede Teilsumme (die nenne ich S(i,j)) zeigt, daß sie kleiner oder gleich etwas ist. Dabei hat man es mit sehr unangenehmen Indexrechnungen zu tun. Aber um zu verstehen, was ich meine, kannst Du ja mal die Teilsummen bilden. Auch wenn Du das dann nicht formal hinbekommst, hast Du dennoch etwas verstanden.

    8. Teilbarkeit
      1. Beweise: 47 ist ein Teiler von 7(2n) - 2n

        Der Induktionsanfang ist klar
        n=1 => 72 - 21 = 47; 47 ist Teiler von 47
        und die Induktionsbehauptung auch: A(n+1): 47 ist ein Teiler von 7(2n+2) - 2(n+1)
        Wie kann ich diesen Ausdruck vereinfachen, so daß eine Aussage stehen bleibt, von der auch 47 Teiler ist.

        Ganz einfach:
        72n - 2n = [72]n - 2n.
        Induktionsschritt:
        [72]n+1 - 2n+1
        = [72]n*[72] - 2n+1
        Ergänze in der Klammer -2 und hinter der Klammer
        mache das durch +2*[72]n wieder gut.
        = [72]n*[72-2] +2*[72]n - 2*2n
        = [72]n*[72-2] + 2*[72]n - 2*2n
        = [72]n*[72-2] + 2*( [72]n - 2n )
        Jeder der beiden Summanden enthält also einen Faktor, der nach Induktionsvoraussetzung durch 47 teilbar ist. Folglich ist der gesamte Ausdruck durch 47 teilbar.

      Fraktal

    9. Zahlentheorie
      1. Behauptung: Es gibt unendlich viele Primzahlen

        Der geforderte Beweis wird oft durch Widerspruch geführt. Ich will das zunächst auch tun. Als zweiten Beweis gebe ich dann noch den durch vollst. Induktion. Man wird sehen, daß der Widerspruchsbeweis umständlicher ist. Es wird nämlich der Widerspruch genau mit der konstruktiven Idee für die vollst. Induktion erzeugt.

        Wenn es wirklich unendlich viele Primzahlen gibt, kann man sicher nicht alle Primzahlen aufschreiben. Aber man kann die Möglichkeit prüfen, daß es nur endlich viele Primzahlen gibt und diese Möglichkeit konsequent weiter denken. Am Ende dieser Überlegung wird man feststellen, daß etwas nicht stimmt. Und wenn ein aufgrund logischer Gesetze entstandenes Endergebnis offensichtlich nicht wahr sein kann, ist erwiesen, daß auch die am Anfang getroffene Annahme nicht wahr sein kann. Aus etwas richtigem kann nach der mathematischen Logik niemals etwas falsches folgen. Diese Beweistechnik nennt man einen Widerspruchsbeweis.

        Angenommen es gäbe nur endlich viele Primzahlen p1,....,pn.
        Dann betrachte die Zahl p=p1*...*pn+1, welche offensichtlich durch keines der pi, i=1,...,n teilbar ist. Dann muß p, welches ja von allen pi verschieden ist, offensichtlich eine Primzahl sein.
        Das ist ein Widerspruch zur Annahme.
        Also war die Annahme falsch, es muß demnach unendlich viele Primzahlen geben.

        Der Beweis enthält eine konstruktive Idee, wie man aus den ersten n Primzahlen eine weitere Zahl konstruieren kann, durch die man die Existenz einer weiteren, der (n+1)-ten Primzahl, nachweisen kann .
        Anstatt einen Beweis durch Widerspruch zu führen, hätte man auch den direkten Beweis führen können. Der geht dann so:

        Es seien die ersten n Primzahlen bekannt. Dann betrachte Zahl q = p1*...*pn+1, welche offensichtlich durch keines der pi, i=1,...,n teilbar ist.

        Wir wissen nicht, ob q eine Primzahl ist, darum betrachten wir jetzt beide Möglichkeiten.
        Fall 1: q ist eine Primzahl. Dann haben wir eine weitere Primzahl gefunden.
        Fall 2: q ist keine Primzahl. Dann gibt es einen echten Teiler von q. (Ein echter Teiler ist weder die 1 noch q selbst).
        Diese Teiler ist nach Konstruktion von q keine der Primzahlen p1, ... , pn. Es muß demnach eine weitere Primzahl geben, die q teilt. Diese "andere" Primzahl ist größer als pn. Ich nenne diese neue Primzahl p*. p* ist nicht notwendigerweise die n+1 -te Primzahl (es kann zwischen der größten Primzahl unter den ersten n Primzahlen und der neuen Primzahl noch andere Primzahlen geben), aber aus der Existenz von n Primzahlen folgt die Existenz von mindestens n+1 Primzahlen. Diese Art zu schließen ist die vollständige Induktion. Als Induktionsanfang genügt die Existenz einer Primzahl. Ausgehend von p1=2 weist man so die Existenz einer weiteren Primzahl nach.

        Wer sich nun fragt, ob denn q nicht immer eine Primzahl ist, dem gebe ich ein Gegenbeispiel:
        2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 ist keine Primzahl, denn 30031 = 59 * 509.

        Im Induktionsschritt muß man deshalb vorsichtig sein.
        Aus den ersten n Primzahlen p1,....,pn ergibt sich die Existenz einer weiteren. Wie diese neue Primzahl aber lautet, sagt der Beweis nicht.
        Und die Primzahl p* ist nicht notwendig die (n+1)-te Primzahl. Aber wenn es bis zu p* mehr als n+1 Primzahlen gibt, dann ist das ja auch genug. Man sucht dann aus den mehr als n+1 Primzahlen die ersten n+1 heraus und kann damit den Induktionsschritt von n+1 auf n+2 durchführen.

    10. Rekursiv definierte Folgen
      1. Für die Fibonacci Zahlen u1=1, u2=1 und un+1=un + un-1, n ÎN ist zu zeigen:
        un+m = un-1*um + un*um+1
        Beweis mit Induktion über m.
        Für m=1 also un-1*u1 + un*u2
        = un-1*1 + un*1 = un-1 + un. OK.
        Nun un+(m+1) = un+m + un+m-1
        Für un+m und un+m-1 die Induktionsvoraussetzung anwenden, vereinfachen, umsortieren usw. Führt zum Ergebnis.
      2. Die Folge a(n) sei rekursiv definiert durch die folgende Formel:

        a(n+1) = 1 + 2a(n-1) + Sn-1 k=0 a(k)
        Bestimme eine explizite Formel für a(n) (für alle nÎN+).

        Anfangswerte sind a(0) = 1
        a(1) = 2
        Ich rechne zuerst einige weitere Folgenglieder aus:
        a(2) = 1 + 3*a(0) + S-1 k=0 a(k)
        Die Summe hat also keine Summanden!
        => a(2) = 1+3*1 = 4

        a(3) = 1 + 3*a(1) + S0 k=0 a(k)
        Die Summe hat nur einen Summanden: k=0!
        => a(3) = 1+3*a(1) + a(0) = 1 + 3*2 + 1 = 8

        a(4) = 1 + 3*a(2) + S1 k=0 a(k)
        Die Summe hat zwei Summanden: k=0 und k=1!
        => a(4) = 1+3*a(2) + a(0) + a(1) = 1 + 3*4 + 1 + 2 = 16

        a(5) = 1 + 3*a(3) + S2 k=0 a(k)
        => a(5) = 1+3*a(3) + a(0) + a(1) + a(2) = 1 + 3*8 + 1 + 2 + 4 = 32

        Das sieht so aus, als ob a(n) = 2n sein könnte.
        Diese Vermutung habe ich durch die ersten berechneten Folgenglieder gefunden.

        Ich weiß noch nicht, ob diese Vermutung richtig ist, aber ich will versuchen sie zu beweisen.
        Wenn ich a(n) = 2n beweisen kann, dann habe ich die geforderte Formel für a(n).

        Beweis mit vollständiger Induktion.
        Die Behauptung a(n) = 2n ist richtig für n=1,2,3,4 und 5 (wie man oben gesehen hat).
        Nun zum Induktionsschritt. Wir wissen, daß für alle n£n0 gilt: a(n) = 2n.

        a(n+1) = 1 + 2a(n-1) + Sn-1 k=0 a(k) = 1 + 2*2n-1 + Sn-1 k=0 2k

        Die Summe Sn-1 k=0 2k ist gleich (2n-1)/(2-1). Diese Formel ist bekannt, denn es handelt sich um eine geometrische Reihe mit q=2.

        Das setze ich ein:
        a(n+1) = 1 + 2*2n-1 + (2n-1-1)/(2-1) = 1 + 2*2n-1 + 2n - 1 = 2n + 2n = 2n+1
        Genau das wollten wir zeigen.
        Also gilt für alle n: a(n) = 2n

      3. Gegeben ist die Folge: a1= 2, an+1=2-1/an.
        Zeige an=(n+1)/n

        Die schwierigere Frage bei rekursiv definierten Folgen ist die, wie man eine geschlossene Form findet. In dieser Aufgabe ist die Vermutung an=(n+1)/n nach einigen ausgerechneten Werten leicht zu raten.
        Um jetzt die Vermutung zu beweisen, muß man nichts besonderes beachten. Ziel ist eine vollständige Induktion.
        Für n=1 ist die Behauptung wahr.
        Und nun der Schluß von n auf n+1.
        Wenn also die Behauptung an=(n+1)/n wahr ist,
        dann ist jetzt zu zeigen, daß auch an+1=(n+2)/(n+1) wahr ist.

        Wegen der rekursiven Definition ist an+1=2-1/an. [*]
        Und nach Voraussetzung der vollständigen Induktion hier: an = (n+1)/n. [**]
        Gleichung [**] in [*] einsetzen, umformen und umordnen, dann steht da
        an+1=2-n/(n+1) = (2n+2-n)/(n+1) ) (n+2)/(n+1).
        Das war zu zeigen.

        Das Problem bei dieser Aufgabe ist eher, daß sie sehr einfach ist und man Mühe hat, keinen Beweisschritt auszulassen.

        Was waren die Schritte:

        1. Induktionsanfang nachprüfen: a2
        2. Induktionsbehauptung aufstellen: an+1
        3. an+1 mittels der gegebenen Rekursion ausdrücken. In dem Ausdruck kommt an vor.
        4. an durch die für n schon erlaubte Formel ersetzen und in Ausdruck aus 3. einsetzen.
        5. Ersetzen Ausdruck aus 3. umformen, bis man das gewünschte Ergebnis sieht.

      Fraktal

    11. Eindeutigkeitsbeweis

      1. Zeige, daß die Repräsentation von ganzen Zahlen zur Basis 3 mit den Ziffern {-1,0,1} eindeutig ist!

        Sei nÎZ und nehmen wir an, daß es zwei verschiedene Repräsentationen gibt.
        Also einerseits Sk i=0 ai*3i = n
        und andererseits Sl i=0 bi*3i = n.
        Wir können o.B.d.A annehmen, daß k³l, ansonsten vertauschen wir eben k und l.
        Außerdem können wir, falls l<k ist, die zweite Summe auch bis k laufen lassen mit Koeffizienten bi=0 für l<i£k.
        Dann haben wir in beiden Summen gleich viele Summanden. Jetzt bilde die Differenz:
        Sk i=0 ai*3i - Sk i=0 bi*3i
        = Sk i=0 (ai-bi)*3i = 0
        Beweise nun, daß die Koeffizienten alle Null sind und zwar durch vollständige Induktion über k.
        k=0 => (a0-b0)*1 = 0 => a0 = b0
        Nun k->k+1. Hinschreiben, dann umsortieren und schließlich:
        Sk i=0 (ai-bi)*3i = (bk+1-ak+1)*3k+1
        Man sieht, die rechte Seite der Gleichung ist durch 3k+1 teilbar. Da auf der linken Seite nur kleiner Dreierpotenzen vorkommen
        und außerdem -2 < ai-bi < 2 für alle 0£ i £ k, folgt daß bk+1-ak+1=0. Auf den Rest der Darstellung wende die Induktionsvoraussetzung an (hat ja Summe bis k). Immer gilt ai = bi.
        Fertig.
        Achtung: Hier wurde nicht gezeigt, daß die geforderte Darstellung existiert. Es wurde gezeigt, daß die Darstellung eindeutig ist, falls sie existiert. Wir haben immer noch keine Ahnung, wie man eine solche Darstellung für ein n ausrechnen kann. Mehr war aber nicht verlangt.

    12. Differentialrechnung
      1. Beweis der Potenzregel für ganzzahlige negative Exponenten anhand der Quotienten- und Kettenregel:
        Die Ableitung von f(x)=x-n ist f'(x)=-n*x-n-1

        Die Funktion f(x)=x-n=1/xn kann man auch schreiben als f(x)=g(x)/h(x) mit g(x)=1 und h(x)=xn.
        Die Quotientenregel sagt f'(x)=[g'(x)*h(x)-g(x)*h'(x)]/(h(x))2
        Wenn schon als bekannt benutzt werden darf, daß h'(x)=n*xn-1, dann erhält man:
        f'(x) = [0*h(x)-1*n*xn-1]/x2n = -n*xn-1/x2n = -n/xn+1 = -n*x-n-1

        Wenn h'(x)=n*xn-1 auch bewiesen werden soll, dann mache das mit Induktion unter Verwendung der Produktregel.

        Bemerkung:
        Ich drücke die Funktion f(x) als Quotient der Funktionen g(x)/h(x) aus.
        Die Regel für die Ableitung von Quotienten ist schon bekannt, und ich benutzte sie.
        Der Sinn dieses Ansatzes ist, die negativen Exponenten in positive Exponenten von Funktionen im Nenner eines Quotienten zu verwandeln.
        Dann setze ich für g, g', h und h' die jeweiligen Ableitungen ein. Für g(x)=1 ist g'(x)=0. Für h(x)=xn ist h'(x)=n*xn-1.
        Mit etwas Termumformung und den Potenzrechenregeln (xn-1/x2n ist gleich 1/xn+1, denn 2n-(n-1) ist n+1) komme ich dann zum Ergebnis.
        Und auch wegen der Potenzrechenregeln ist (xn)² = (x2n)

    Fraktal

  15. Zum Schluß

    Das Induktionsargument ist in fast allen Gebieten der Mathematik verbreitet. Je fortgeschrittener aber das Thema, desto kürzer fallen die Beweise aus oder werden gar nicht mehr ausgeführt. Evtl. schreibt der Autor einer mathematischen Arbeit noch "Kann man durch Induktion zeigen". Wie einige meiner Beispiele zeigen, erfordern ausführliche Induktionsbeweise einigen Platz. Den spart man sich häufig zugunsten der Lesbarkeit von mathematischen Texten. Auch hat man in den Publikationsblättern ja oft nur wenige Seiten zur Verfügung. Die Arbeit, die veröffentlicht werden soll, muß gegenüber der vorhandenen Ausarbeitung deutlich gekürzt werden.
    Das Induktionsprinzip ist von Mathematikern derart verinnerlicht, daß sie es intuitiv schon sehen, wo und wie eine Induktion angesetzt werden kann und dankbar sind für die Auslassung unnötiger Details. Es genügt die Beschreibung der Idee ("füge eine neue Gerade hinzu ...") um einen Beweis zu geben, bzw. es genügt, den ausführlichen und genauen Beweis in der Hinterhand zu haben, falls irgendwelche Zweifel an der Richtigkeit auftauchen.

    Weiterführende Links bei Matroids Matheplanet.

    Sehr schöne und von der Idee her abwechslungsreiche Induktionsbeweise gibt es auch in der Kombinatorik und Graphentheorie (Induktion über die maximale Valenz einer Ecke). Vielleicht schreibe ich darüber das nächste mal.


Zurück zum Seitenanfang


Martin Wohlgemuth für Matroids Matheplanet 16.4.2001 (letzte Änderung 21.9.2010).
[Die im Text verwendeten Bilder mit Fraktalen habe ich mit Ultra Fractal erstellt. Mehr über Fraktale bei Matroids Fraktale.]


 

Dieser Artikel ist in unserem Buch enthalten:
Mathematisch für Anfänger
Mathematisch für Anfänger


Mehr von Matroid [Volumenberechnung eines Ringes mit konstanter Höhe] [Lösung von Extremwertaufgaben mit Differentialrechnung] [Ein Problem aus der Stahlindustrie] [Über die Anzahl von Sitzordnungen am runden Tisch] [Schachbrettaufgaben]