1. Zusammenfassung Induktionsverfahren

1. Peano-Axiome

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

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]

Wie funktioniert die vollständige Induktion?

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.

Kann man denn wirklich den Induktionsschluß unendlich oft anwenden?

Was ist schwer an der vollständigen Induktion?

Kann man denn Induktion immer anwenden?

Induktion kann man nicht anwenden, wenn ...

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.

Anwendungen der vollständigen Induktion

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.

      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
        = (n²-5n+4)/2 + n -2
        = (n²-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 (n²+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 (1²+1+2)/2 ist gleich 2.

      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 = (n² + n + 2) / 2 + ( n + 1 ).
      Man kann dann zeigen, daß dies gleich ((n+1)² + (n+1) + 2) / 2 ist.

   3. Anzahl de Rechtecke in einem quadratischen Gitter. Induktion über die Summe der Zeilen und Spalten.
      
   4. Aufgabe: In der Ebene seien n Punkte A₁,A₂,...,A_n 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).

      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)|=2^m.

      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=2⁰.
      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) = 2ⁿ 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 = 2ⁿ, denn es handelt sich auch hier um alle Teilmengen einer Menge mit n Elementen.
      Addiere nun die Anzahlen für a) und b)
      2ⁿ + 2ⁿ = 2ⁿ⁺¹.
      Fertig.



3. Binomialkoeffizienten

1. Beweise Sⁿ _k=0 (^a+k_k) = (^a+n+1_n)
   
   Beweis mit Induktion:
   n=0: (^a+0₀) = (^a+0+1₀). 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:
   Sⁿ⁺¹ _k=0 (^a+k_k) = (^a+(n+1)+1_n+1)
   Also immer da wo n stand, muß jetzt n+1 stehen.
   
   Zum Beweis:
   Sⁿ⁺¹ _k=0 (^a+k_k)
   = Sⁿ _k=0 (^a+k_k) + (^a+n+1_n+1)
   = (^a+n+1_n) + (^a+n+1_n+1)
   = (^a+(n+1)+1_n+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:
   (ⁿ_k-1)+(ⁿ_k) = (ⁿ⁺¹_k)
   [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)ⁿ=Sⁿ _v=0(ⁿ_v) * x^v
   

   Auch das geht mit Induktion.
   Für n=0 steht da (1+x)⁰ = (⁰₀)*x⁰ und das ist richig.
   Für n=1: 1+x = (¹₀)*x⁰ + (¹₁)*x¹ auch richtig.
   Nun der Induktionsschritt:
   (1+x)ⁿ⁺¹ = (1+x)ⁿ * (1+x)
   = (1+x) * Sⁿ _i=0 (ⁿ_i)*xⁱ
   = 1* Sⁿ _i=0 (ⁿ_i)*xⁱ + x* Sⁿ _i=0 (ⁿ_i)*xⁱ
   = Sⁿ _i=0 (ⁿ_i)*xⁱ + Sⁿ _i=0 (ⁿ_i)*xⁱ⁺¹
   jetzt verschiebe ich den Index in der zweiten Summe.
   = Sⁿ _i=0 (ⁿ_i)*xⁱ + Sⁿ⁺¹ _i=1 (ⁿ_i-1)*xⁱ
   In den beiden Summen kommen die Potenzen x¹ bis xⁿ vor. Aber x⁰ ist nur in der ersten Summe und xⁿ⁺¹ nur in der zweiten Summe. Ich zerlege die Summen dementsprechend.
   = 1 + Sⁿ _i=1 (ⁿ_i)*xⁱ + Sⁿ _i=1 (ⁿ_i-1)*xⁱ + xⁿ⁺¹
   Und dann kann ich die beiden Summen zusameenfassen:
   = 1 + Sⁿ _i=1 [(ⁿ_i) + (ⁿ_i-1) ]*xⁱ + xⁿ⁺¹
   Nun gilt für die Binomialkoeffizienten die folgende Beziehung: (ⁿ_i) + (ⁿ_i-1) = (ⁿ⁺¹_i)
   Das eingesetzt ergibt:
   = 1 + Sⁿ _i=1 (ⁿ⁺¹_i)*xⁱ + xⁿ⁺¹
   und dann
   = Sⁿ⁺¹ _i=0 (ⁿ⁺¹_i)*xⁱ

3. Beweis des Binomischen Lehrsatzes
   Beweise:
   (a+b)ⁿ = Sⁿ _i=0 (ⁿ_i) aⁱb^n-i
   Vollständige Induktion.
   n=0 => 1 = 1 stimmt!
   Induktionsschritt:
   (a+b)ⁿ⁺¹ = [ Sⁿ _i=0 (ⁿ_i) aⁱb^n-i ]*(a+b)
   unter Verwendung der Induktionsvoraussetung (für n).
   = a*Sⁿ _i=0 (ⁿ_i) aⁱb^n-i + b* Sⁿ _i=0 (ⁿ_i) aⁱb^n-i
   = Sⁿ _i=0 (ⁿ_i) aⁱ⁺¹b^n-i + Sⁿ _i=0 (ⁿ_i) aⁱb^n-i+1
   = aⁿ⁺¹ + S^n-1 _i=0 n!/(i!*(n-i)!) aⁱ⁺¹b^n-i + bⁿ⁺¹ + Sⁿ _i=1 n!/(i!*(n-i)!) aⁱb^n-i+1
   
   Was passiert denn hier eigentlich?
   Um besser durchzublicken, schreibe ich die Formeln für n=3:
   (a+b)³ = [ a³ + 3a²b¹ + 3a¹b² + b³]*(a+b)
   = a *[ a³ + 3a²b¹ + 3a¹b² + b³] + b*[ a³ + 3a³b¹ + 3a¹b² + b³]
   = a⁴ + 3a³b¹ + 3a²b² + a¹b³ + a³a¹ + 3a²b² + 3a¹b³ + b⁴
   Die gemischten Potenzen kommen je zweimal vor, die Potenzen "hoch 4" je einmal. Ich ordne um:
   = a⁴ + (3+1)*a³b¹ + (3+3)*a²b² + (1+3)*a¹b³ + b⁴
   Aha, der Koeffizient vor a³b¹ ist die Summe von zwei anderen Binomialkoeffizienten. Und zwar (ⁿ_k-1)+(ⁿ_k) und das ist (ⁿ⁺¹_k).
   Und da haben wir die Formel für n=4.

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



4. 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 a₁, ... ,a_n positive reelle Zahlen.
   Dann gilt:
   

   Wir beweisen zuerst folgenden

   Hilfssatz: Gilt für reelle Zahlen b₁, ... ,b_n:
   P_k=1ⁿ b_k = 1, so ist S_k=1ⁿ b_k >= n
   Gleichheit gilt genau dann, wenn b₁=b₂=...=b_n.

   Beweis des Hilfssatzes mit vollständiger Induktion über n.
   Für n=1 gilt die Behauptung.
   Betrachte nun die Zahlen b₁,...,b_n,b_n+1.
   Wenn alle b_i gleich sind und P_k=1ⁿ b_k = 1, dann folgt, daß alle b_i=1,
   und es ist klar, daß S_k=1ⁿ b_k = n+1.
   Falls aber nicht alle b_i=1 sind,
   dann ist o.B.d.A. b₁ < 1 < b₂ weil P_k=1ⁿ b_k = 1.
   Aus b₁ < 1 < b₂ folgt, daß (1 - b₁)*(b₂ - 1) > 0.
   Ausmultipliziert ist das: b₁ + b₂ > 1 + b₁*b₂.

   Aus der Induktionsvoraussetzung folgt für die n Zahlen

   b₁*b₂, b₃, ... ,b_n, b_n+1:

   b₁*b₂ + S_k=3ⁿ⁺¹ b_k >= n.

   Insgesamt erhält man:
   .
   qed.

   Zurück zum Beweis der Behauptung über geometrisches und arithmetisches Mittel
   Wenn a₁ = a₂ = ... = a_n, dann ist die Behauptung trivial, und die Ungleichung gilt mit Gleichheit.

   Nehmen wir also an, daß die a_i nicht alle gleich sind.
   Sei G := .
   Betrachte b_i := a_i / G.

   Nach Konstruktion ist P_k=1ⁿ b_k = 1.
   Da nicht alle b_i gleich sind, folgt aus dem Hilfssatz:
   
   QED.



5. 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 = (k²+k)/2 + (2k+2)/2 = (k²+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+....+n² = n*(n+1)*(2n+1)/6
   Für n=1, ist Sⁿ _k=1 n² = 1. ok.
   Nun Sⁿ⁺¹ _k=1 n² = Sⁿ _k=1 n² + (n+1)² = n * (n+1) * (2n+1)/6 + (n+1)²
   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)² - (n+1) * (n+2) * (2(n+1)+1)/6 = 0
   Kräftig ausmultiplizieren, dann sieht man's.
   Bemerkung: Ich habe Sⁿ⁺¹ _k=1 n² zuerst so geschrieben: Sⁿ _k=1 n² + (n+1)².
   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:
   Sⁿ _k=1 n² = n*(n+1)*(2n+1)/6.
   
   Also ist
   Sⁿ⁺¹ _k=1 n² = n*(n+1)*(2n+1)/6 + (n+1)².
   
   Was wir zum Nachweis der Behauptung gern sehen möchten, ist, daß
   Sⁿ⁺¹ _k=1 n² = (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 Sⁿ _i=1 i³ = (Sⁿ _i=1 i )²

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



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



6. Abschätzungen
   1. Man beweise: n/2 < S^2n-1 _i=1(1 / i) < n
      Induktion.
      Anfang: n=2. Stimmt.
      Dann S^2n+1-1 _i=1 1/i = S^2n-1 _i=1 1/i + S^2n+1-1 _i=2ⁿ 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/2²ⁿ ab. Insgesamt sind es 2²ⁿ Summanden, also kann die zweite Summe gegen 1 abgeschätzt werden.
      Folglich ist
      = S^2n-1 _i=1 1/i + S^2n+1-1 _i=2ⁿ 1/i < n + 1. Das war der eine Teil.
      Und die Abschätzung nach unten: Schätze jeden Summanden der zweiten Summe gegen 1/2ⁿ⁺¹ ab. Es sind 2ⁿ 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)=S^m _i=n a(i), also die Summe über m-n+1 Folgenglieder, beginnend bei a(m).

      Beispiele
      S(1,1)=S¹ _i=1 a(i) = 1/3
      S(2,4)=S⁴ _i=2 a(i) = 1/15 + 1/35 + 1/63 = 1/9
      S(5,12)=S¹² _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 3^k Summanden addieren (k³0) und deren Summe ist gleich 1 / 3^k+1.
      Also:
      Die ersten 3⁰ Summanden addiert, ergibt 1/3¹.
      Die nächsten 3¹ Summanden addiert, ergibt 1/3².
      usw.
      
      Es läuft darauf hinaus, daß Sⁿ _i=1 a(i) <= S^x _k=0 S(y,z) = S^x _i=1 (1/3)ⁱ. 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-qⁿ)/(1-q). Ohne 0-Term ist die Summe (1-qⁿ)/(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 Sⁿ _i=1 a(i) <= S^x _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.

7. Teilbarkeit

1. Beweise: 47 ist ein Teiler von 7⁽²ⁿ⁾ - 2ⁿ

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

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



8. 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 p₁,....,p_n.
   Dann betrachte die Zahl p=p₁*...*p_n+1, welche offensichtlich durch keines der p_i, i=1,...,n teilbar ist. Dann muß p, welches ja von allen p_i 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 = p₁*...*p_n+1, welche offensichtlich durch keines der p_i, 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 p₁, ... , p_n. Es muß demnach eine weitere Primzahl geben, die q teilt. Diese "andere" Primzahl ist größer als p_n. 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 p₁=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 p₁,....,p_n 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.

9. Rekursiv definierte Folgen

1. Für die Fibonacci Zahlen u₁=1, u₂=1 und u_n+1=u_n + u_n-1, n ÎN ist zu zeigen:
   u_n+m = u_n-1*u_m + u_n*u_m+1
   Beweis mit Induktion über m.
   Für m=1 also u_n-1*u₁ + u_n*u₂
   = u_n-1*1 + u_n*1 = u_n-1 + u_n. OK.
   Nun u_n+(m+1) = u_n+m + u_n+m-1
   Für u_n+m und u_n+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) + S^n-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) + S⁰ _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) + S¹ _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) + S² _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) = 2ⁿ 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) = 2ⁿ beweisen kann, dann habe ich die geforderte Formel für a(n).
   
   Beweis mit vollständiger Induktion.
   Die Behauptung a(n) = 2ⁿ 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£n₀ gilt: a(n) = 2ⁿ.
   
   a(n+1) = 1 + 2a(n-1) + S^n-1 _k=0 a(k) = 1 + 2*2^n-1 + S^n-1 _k=0 2^k
   
   Die Summe S^n-1 _k=0 2^k ist gleich (2ⁿ-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*2^n-1 + (2^n-1-1)/(2-1) = 1 + 2*2^n-1 + 2ⁿ - 1 = 2ⁿ + 2ⁿ = 2ⁿ⁺¹
   Genau das wollten wir zeigen.
   Also gilt für alle n: a(n) = 2ⁿ

3. Gegeben ist die Folge: a₁= 2, a_n+1=2-1/a_n.
   Zeige a_n=(n+1)/n

   Die schwierigere Frage bei rekursiv definierten Folgen ist die, wie man eine geschlossene Form findet. In dieser Aufgabe ist die Vermutung a_n=(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 a_n=(n+1)/n wahr ist,
   dann ist jetzt zu zeigen, daß auch a_n+1=(n+2)/(n+1) wahr ist.
   
   Wegen der rekursiven Definition ist a_n+1=2-1/a_n. [*]
   Und nach Voraussetzung der vollständigen Induktion hier: a_n = (n+1)/n. [**]
   Gleichung [**] in [*] einsetzen, umformen und umordnen, dann steht da
   a_n+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: a₂
   2. Induktionsbehauptung aufstellen: a_n+1
   3. a_n+1 mittels der gegebenen Rekursion ausdrücken. In dem Ausdruck kommt a_n vor.
   4. a_n 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.



10. 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 S^k _i=0 a_i*3ⁱ = n
       und andererseits S^l _i=0 b_i*3ⁱ = 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 b_i=0 für l<i£k.
       Dann haben wir in beiden Summen gleich viele Summanden. Jetzt bilde die Differenz:
       S^k _i=0 a_i*3ⁱ - S^k _i=0 b_i*3ⁱ
       = S^k _i=0 (a_i-b_i)*3ⁱ = 0
       Beweise nun, daß die Koeffizienten alle Null sind und zwar durch vollständige Induktion über k.
       k=0 => (a₀-b₀)*1 = 0 => a₀ = b₀
       Nun k->k+1. Hinschreiben, dann umsortieren und schließlich:
       S^k _i=0 (a_i-b_i)*3ⁱ = (b_k+1-a_k+1)*3^k+1
       Man sieht, die rechte Seite der Gleichung ist durch 3^k+1 teilbar. Da auf der linken Seite nur kleiner Dreierpotenzen vorkommen
       und außerdem -2 < a_i-b_i < 2 für alle 0£ i £ k, folgt daß b_k+1-a_k+1=0. Auf den Rest der Darstellung wende die Induktionsvoraussetzung an (hat ja Summe bis k). Immer gilt a_i = b_i.
       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.

11. 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/xⁿ kann man auch schreiben als f(x)=g(x)/h(x) mit g(x)=1 und h(x)=xⁿ.
   Die Quotientenregel sagt f'(x)=[g'(x)*h(x)-g(x)*h'(x)]/(h(x))²
   Wenn schon als bekannt benutzt werden darf, daß h'(x)=n*x^n-1, dann erhält man:
   f'(x) = [0*h(x)-1*n*x^n-1]/x²ⁿ = -n*x^n-1/x²ⁿ = -n/xⁿ⁺¹ = -n*x^-n-1
   
   Wenn h'(x)=n*x^n-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)=xⁿ ist h'(x)=n*x^n-1.
   Mit etwas Termumformung und den Potenzrechenregeln (x^n-1/x²ⁿ ist gleich 1/xⁿ⁺¹, denn 2n-(n-1) ist n+1) komme ich dann zum Ergebnis.
   Und auch wegen der Potenzrechenregeln ist (xⁿ)² = (x²ⁿ)

Zum Schluß

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.