Induktion (Mathematik)

aus Freepedia, der freien Wissensdatenbank

Vollständige Induktion oder der "Schluss von n auf n + 1" ist eine Beweismethode, die üblicherweise eine Aussage für alle natürlichen Zahlen beweist. Sie funktioniert aber auch für allgemeinere Fälle (siehe unten).

Der Name dieses Beweisverfahrens leitet sich von lat. inductio (= Hereinführung) ab, in der Logik meint man damit den Schluss von speziellen Sachverhalten auf allgemeine Regeln, siehe Induktion (Logik). Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip.

Vereinfacht gesprochen geht es um folgende Argumentation:

Lässt sich die bestimmte Behauptung über natürliche Zahlen für eine gewisse Anfangszahl begründen, und lässt sich außerdem zeigen, dass aus ihrer Geltung für eine beliebige Zahl n ihre Geltung für die nächste Zahl n + 1 folgt, so gilt diese Behauptung für alle auf die Anfangszahl folgenden natürlichen Zahlen.

Inhaltsverzeichnis 1 Definition 1.1 Motivation 1.2 Die Idee 2 Anderes Beispiel: Summe der ungeraden Zahlen 3 Bezeichnungen 4 Indirekte Sichtweise 5 Beweis von Ungleichungen 6 Tipps zur Anwendung 6.1 Häufige Fehler 7 Anwendungen 8 Verallgemeinerungen und Variationen 8.1 Beweis für fast alle natürlichen Zahlen 8.2 Verwendung mehrerer Vorgänger 8.3 Vorwärts-rückwärts-Induktion 8.4 Sonstige 9 Weblinks

Definition

Das Beweisverfahren der vollständigen Induktion beruht auf dem 5. Peano-Axiom für die natürlichen Zahlen <math> \mathbb{N} </math>, dem Induktionsaxiom. Dieses besagt:

Ist <math> K </math> eine Teilmenge von <math>\mathbb{N}</math> mit den Eigenschaften, dass 0 (bzw. 1) in <math> K </math> liegt und für jedes Element <math> k </math> von <math> K </math> auch <math> k +1 </math> in <math> K </math> liegt, dann ist <math> K </math> gleich <math> \mathbb{N} </math>.

(Ob man bei 0 oder 1 beginnt, hängt davon ab, ob 0 als Element von <math> \mathbb{N} </math> gezählt wird. Je nach Zweckmäßigkeit ist dies unterschiedlich definiert.)

Um zu beweisen, dass eine bestimmte logische Formel <math> p(n) </math> für jede beliebige natürliche Zahl <math> n </math> gilt, setzt man <math> K </math> als die Menge aller natürlichen Zahlen <math> k </math>, für die die Aussage <math> p(k) </math> gilt und wendet anschließend das Induktionsverfahren auf diese Menge an. Somit zeigt man, dass die Aussage <math> p(1) </math> wahr ist und damit das Element 1 in <math> K </math> liegt und dass für jede Aussage <math> p(k) </math> auch die Aussage <math> p(k+1) </math> stimmt, sodass auch <math> k </math> und <math> k+1 </math> in der Menge <math> K </math> liegen. Nach dem Induktionsaxiom gilt deshalb <math> K = \mathbb{N} </math> und die Aussage <math> p(n) </math> besitzt für alle natürlichen Zahlen <math> n\ge 1 </math> Gültigkeit.

Motivation

Es wird vermutet, dass eine Aussage für alle natürlichen Zahlen gilt. Bei der gegebenen Problemstellung ist es allerdings noch nicht gelungen, eine für alle natürlichen Zahlen gültige Aussage anzugeben. Da die Menge der natürlichen Zahlen unendlich ist, ist es ebenso nicht möglich die Richtigkeit der Aussage für jede Zahl einzeln zu beweisen. Durch die Methode der vollständigen Induktion kann aber trotzdem gezeigt werden, ob die Aussage für die gesamte Menge richtig ist.

Beispiel

Zu beweisen ist, dass <math>1+2+...+n = \frac{n(n+1)}{2}</math>.

Für einzelne Zahlen ist die Formel leicht nachzurechnen:

• <math>n = 1</math>:

<math>1 = \frac{1(1+1)}{2}</math>

• <math>n = 2</math>:

<math>1 + 2 = 3 = \frac{2(2+1)}{2}</math>

• und so weiter ...

Für den folgenden Beweis reicht bereits der Fall n = 1. Auf der Suche nach einer allgemein gültigen Aussage, wird man die Behauptung konsequenterweise für viele andere <math> n </math> überprüfen.

Die Idee

Ist bekannt,

• dass eine bestimmte Aussage für <math> n = 1 </math> gilt und
• dass sie für jedes beliebige <math> n = k </math> auch für <math> n = k +1 </math> gilt,

dann folgt nach dem Induktionsaxiom, dass die Aussage für alle <math> n </math> gilt.

Auf den ersten Blick scheint das Problem nur anders formuliert worden zu sein, indem die nächste Zahl einfach als die vorhergehende plus 1 bezeichnet wurde. Immer noch sind es unendlich viele Zahlen, doch durch den allgemeinen Ausdruck <math> n=k+1 </math> kann davon ausgegangen werden, dass die Aussage für <math> n=1 </math> bis <math> n=k </math> gilt. Selbst die Formel die man zu beweisen sucht, kann im Beweis als Voraussetzung für Zahlen unterhalb der aktuellen Zahl (das bedeutet unterhalb von <math> k+1 </math>) verwendet werden.

Angewandt auf obiges Beispiel bedeutet dies folgendes:

Angenommen, die Formel wurde bereits bis zur Zahl <math> n=k </math> bewiesen. Nun soll gezeigt werden, dass die Formel für <math> n=k+1 </math> ebenso Gültigkeit besitzt (d.h. nach dem Beispiel soll die Summe <math> 1 + 2 + 3 + \dots + k + (k+1) </math> berechnet werden).

Die ersten <math> k </math> Summanden bilden eine solche Summe, und zwar für <math> k </math>, was kleiner ist als <math> k+1 </math>. Also darf man - durch die Voraussetzung, dass die Formel für <math> n=k </math> bereits bewiesen ist - diesen Schritt abermals anwenden:

<math> 1 + 2 + 3 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)</math>

In diesem Ausdruck wird (<math> k </math>+1) ausgeklammert:

<math>= (k+1) \cdot \left(\frac{k}{2}+1 \right)</math>

und dies weiter umgeformt zu

<math>= (k+1) \cdot \frac{k+2}{2}</math>

<math>= \frac{(k+1)\cdot ((k+1)+1)}{2}</math>

Zu beachten ist, dass <math> k </math> beliebig gewählt werden darf. Beim Vergleich dieses Ausdrucks mit dem zu beweisenden Ausdruck ist festzustellen, dass lediglich <math> k </math> durch <math> k+1 </math> ersetzt ist. Damit ist der Schritt von <math> k </math> zu <math> k+1 </math> für allgemeine Werte von <math> k </math> bewiesen.

Der große Vorteil des Induktionsbeweises zeigt sich darin, dass die Schritte nicht mehr einzeln durchgeführt werden müssen. Bewiesen werden muss nur, dass eine Aussage für die unterste Zahl (entweder 0 oder 1) gilt und ebenso, wenn sie bis zu einer beliebigen Zahl gilt, dass sie auch für die nächste Gültigkeit besitzt. (So ist es theoretisch möglich jede Zahl durch die ständige Anwendung der einzelnen Schritte zu erreichen.)

In der Praxis wird üblicherweise für <math> n </math> und <math> k </math> der gleiche Buchstabe <math> n </math> gewählt. Dies stellt insofern kein Problem dar, solange man sich der unterschiedlichen Bedeutung von <math> n </math> in "<math> p(n) </math> gilt für alle natürlichen Zahlen <math> n </math>" in der zu beweisenden Aussage und "<math> p(n) </math> gilt für ein konkretes <math> n=k </math>" in der Induktionsvoraussetzung bewusst ist. Die Nichtbeachtung führt dazu, dass die zu beweisende Aussage auch als Voraussetzung verwendet wird und es ergibt sich ein (mathematisch wertloser) Zirkelschluss. Ist die zu beweisende Formel hingegen falsch, so führt der Induktionsschritt nicht zum Ziel, die Formel erfüllt den Induktionsanfang nicht, oder es tritt beides auf.

Anderes Beispiel: Summe der ungeraden Zahlen

Es soll eine Formel gefunden werden, die die Summe aller ungeraden Zahlen von 1 bis <math> n </math> vereinfacht und diese Formel soll bewiesen werden:

1 = 1; 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16

Vermutung: Die Summe aller ungeraden Zahlen von 1 bis <math> n </math> ergibt eine Quadratzahl. Genauer gesagt:

<math>\sum^n_{i=1} (2i-1) = n^2</math>

Um diese Formel zu beweisen, müssen die folgenden zwei Punkte erfüllt sein:

1. <math>\sum^1_{i=1} (2i-1) = 1^2</math>
2. Wenn <math>\sum^n_{i=1} (2i-1) = n^2 </math>, so ist <math>\sum^{n+1}_{i=1} (2i-1) = (n+1)^2</math>

Da <math>\sum^1_{i=1} (2i-1) = 1 =1^2</math> ist, ist der erste Punkt erfüllt. Die Richtigkeit des zweiten Punktes zeigt man durch die Gleichung <math>\sum^{n+1}_{i=1} (2i-1) = \sum^n_{i=1} (2i-1) + 2(n+1)-1 = n^2 + 2(n+1)-1 = n^2 + 2n +1 = (n+1)^2</math> (Im letzen Schritt wird eine binomische Formel angewendet).

Damit ist die vollständige Induktion für <math>\sum^n_{i=1} (2i-1) = n^2</math> abgeschlossen und bewiesen.

Bezeichnungen

Den Beweis der Aussage für die erste Zahl nennt man Induktionsanfang, den Beweis für <math> n+1 </math> unter der Annahme (Induktionsannahme, Induktionsvoraussetzung), dass sie bis <math> n </math> gilt, nennt man Induktionsschritt.

Wurden beide Beweisschritte durchgeführt, ist somit die Aussage für alle natürlichen Zahlen bewiesen. In Kurzform:

Gewählt wird eine beliebige aber feste natürliche Zahl <math> N </math> und zeigen, dass die Aussage für <math> N </math> wahr ist:

• Die Aussage ist wahr für <math> n = 0</math> (Induktionsanfang)
• und deshalb für <math> n = 1</math> (Induktionsschritt)
• und deshalb für <math> n = 2</math> (Induktionsschritt)
• ...
• und deshalb für <math> n = N </math> (Induktionsschritt)

Nach endlich vielen Induktionsschritten gelangt man schließlich zur Aussage für <math> N </math>.

Oft wird diese Methode mit dem Dominoeffekt verglichen: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein ein weiterer umgestoßen wird, so fallen schließlich alle Dominosteine.

Indirekte Sichtweise

Eine andere Sichtweise ist die eines indirekten Beweises: Angenommen, die Aussage gälte nicht für alle natürlichen Zahlen. Dann gibt es eine kleinste Zahl <math>n_0</math>, für die sie falsch ist. Es gibt nun zwei Fälle:

• <math>n_0=0</math>: Dies wird durch den Induktionsanfang ausgeschlossen.
• <math>n_0\ne0</math>: Nach Voraussetzung ist <math>n_0</math> die kleinste Zahl, für die die Aussage falsch ist, also ist sie für <math>n_0-1</math> wahr. Wendet man nun den Induktionsschritt an, kann man daraus schließen, dass die Aussage auch für <math>(n_0-1)+1=n_0</math> richtig ist. <math>n_0</math> war aber definiert als die kleinste Zahl, für die die Aussage falsch ist: Widerspruch.

Beide Fälle können also ausgeschlossen werden, damit ist die Aussage für alle natürlichen Zahlen wahr.

Beweis von Ungleichungen

Vollständige Induktion kann auch zum Beweis von Ungleichungen verwendet werden. Diese Beweise sind aber häufig schwieriger als die Beweise von Gleichungen, da sie üblicherweise mehr oder weniger naheliegende Abschätzungen erfordern. Als Beispiel werde folgende Ungleichung bewiesen: Für reelle <math>x_i>0\!</math>, <math>i=1,\dots,n</math> mit <math>\prod_{i=1}^n x_i =1</math> folgt, dass <math>\sum_{i=1}^n x_i \geq n</math>.

Die Bedeutung dieser Ungleichung liegt darin, dass sie in weiterer Folge für den Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet werden kann.

Der Induktionsanfang für den Fall <math>n=1</math> ist offensichtlich. Gilt im Fall <math>n=2</math>, dass <math>x_1=x_2=1</math>, so gilt offensichtlich <math>x_1+x_2 = 2\geq 2</math>. <math>x_1</math> und <math>x_2</math> können nicht beide größer oder beide kleiner als 1 sein. Nimmt man an, dass <math>x_1\leq1</math> und <math>x_2\geq1</math> gilt, so folgt

<math>0\leq(1-x_1)(x_2-1)=x_1+x_2-x_1\cdot x_2 - 1 = x_1+x_2 - 2</math>

wegen <math>x_1\cdot x_2=1</math>, also

<math>2\leq x_1+x_2</math>. Der Fall <math>x_1\geq1</math> und <math>x_2\leq1</math> ist vollkommen analog zu behandeln.

Für den Induktionsschritt sei nun <math>n\geq 2</math>. Zu zeigen ist, dass für beliebige <math>n+1</math> positive <math>x_i\!</math> mit <math>\prod_{i=1}^{n+1} x_i =1</math> folgt, dass <math>\sum_{i=1}^{n+1} x_i \geq n+1</math>. Als Induktionsvoraussetzung darf angenommen werden, dass für <math>n</math> andere beliebige Zahlen (zur einfacheren Unterscheidung nennen wir sie <math>y_i</math>) aus <math>\prod_{i=1}^{n} y_i =1</math> die Ungleichung <math>\sum_{i=1}^{n} y_i \geq n</math> folgt.

Sind alle <math>x_i=1</math>, so gilt <math>\sum_{i=1}^{n+1} x_i = n+1</math> und der Beweis ist fertig. Andernfalls gibt es mindestens ein <math>x_i> 1 </math>, sonst wäre das Produkt <math>\prod_{i=1}^{n+1} x_i <1</math>; ebenso gibt es ein anderes <math>x_i<1</math>. O. B. d. A. sei also <math>x_n<1</math> und <math>x_{n+1}>1</math>. Die Bedeutung dieser Wahl wird erst später klar.

Setzt man nun <math>y_i=x_i</math> für <math>i=1,\dots,n-1</math> und <math>y_n=x_n\cdot x_{n+1}</math>, so gilt

<math>\prod_{i=1}^{n} y_i = \prod_{i=1}^{n+1} x_i =1</math>.

Somit kann die Induktionsvoraussetzung angewendet werden und es folgt

<math> n\leq \sum_{i=1}^{n} y_i = \sum_{i=1}^{n-1} x_i + x_n\cdot x_{n+1}</math>.

Nun kommt ins Spiel, dass die Indizes <math>n</math> und <math>n+1</math> so gewählt wurden, dass <math>x_n<1</math> und <math>x_{n+1}>1</math> gilt. Daraus folgt nämlich

<math>0\leq \left(1-x_n\right)\left(x_{n+1}-1\right)=x_n+x_{n+1}-x_n\cdot x_{n+1} -1</math>.

Addiert man die beiden Ungleichungen, so erhält man

<math>n\leq \sum_{i=1}^{n-1} x_i + x_n+ x_{n+1} -1 = \sum_{i=1}^{n+1} x_i -1</math>,

also genau die Behauptung

<math>n+1 \leq \sum_{i=1}^{n+1} x_i </math>.

Tipps zur Anwendung

Es kann sich beim Beweis von Summenformeln mitunter als sehr mühsam erweisen, beim Induktionsschritt von <math> n </math> zu <math> n+1 </math> durch Umformungen die Struktur der Ausgangsformel neu zu konstruieren. Dies ist jedoch zur Beweisführung unerlässlich. Da ist es dann manchmal hilfreich, das Pferd von hinten aufzuzäumen. Beispielsweise ist das Ausmultiplizieren und Zusammenfassen von Gliedern oftmals leichter zu bewerkstelligen als das phantasievolle Aufspalten und Umordnen von Gliedern, um etwas ausklammern zu können. Um diesen Umstand zu nutzen, setzt man in die zu beweisende Formel <math> n+1 </math> für <math> n </math> ein und versucht, durch äquivalente Umformungen die Ausgangsformel für <math> n </math> zu isolieren. Da die Formel für <math> n </math> laut Voraussetzung gilt, ist der Beweis geführt, sobald das, was bei den äquivalenten Umformungen außer der isolierten Formel z. B. als Summand oder als zusätzlicher Faktor entsteht, dem entspricht, was beim Induktionsschritt hinzugefügt wird.

Häufige Fehler

Beim Beweis durch Induktion treten zwei Fehler besonders häufig auf.

• Der Induktionsschritt funktioniert zwar, die Behauptung gilt für die Anfangsbedingung aber nicht. Man könnte z.B. behaupten, dass

<math>1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} + 7</math>.

Falls diese Behauptung für ein n gelten würde, dann würde sie auch für <math>n + 1</math> gelten! Da sie aber für <math>n = 1</math> nicht gilt, ist sie falsch!

• Beim Induktionsschritt beruft man sich auf einen Fall, der aber nicht explizit bewiesen wurde (z.B. den Fall <math>n = 2</math>). Hier ein Beispiel für so einen falschen Beweis:

Behauptung: Alle Zahlen sind gleich.

Beweis: Wir vergleichen Mengen von Zahlen, dabei sei <math> n </math> die Anzahl der Elemente der Menge.

Induktionsbeginn: Für <math> n = 1 </math> sind alle Elemente der Menge gleich, es gibt ja nur eines!

Induktionsvoraussetzung: Angenommen, in einer Menge mit <math> n </math> Zahlen sind stets alle Zahlen gleich

Induktionsschluss: Dann sind auch alle Zahlen in einer Menge mit <math>n + 1</math> Zahlen gleich, denn: Entfernt man aus der <math>n + 1</math>-elementigen Menge eine Zahl <math> x </math>, dann erhalten wir eine <math> n </math>-elementige Menge, in der nach Voraussetzung alle Zahlen gleich sind. Fügen wir <math> x </math> wieder hinzu und entfernen eine andere Zahl <math> y </math>, dann sind wieder alle Zahlen der Restmenge gleich. Es folgt, dass <math>x = y</math> gelten muss, also sind alle Zahlen der Menge gleich.

Der Fehler liegt darin, dass man nur dann verschiedene Zahlen <math> x </math> und <math> y </math> entfernen kann, wenn die Menge mindestens 2 Elemente hat. Wir berufen uns also auf die Richtigkeit von <math>n = 2</math>, ohne es vorher bewiesen zu haben. Dass der Fall für <math>n = 1</math> richtig ist hilft uns nicht, da auf diesen Fall der Induktionsschritt überhaupt nicht anwendbar ist!

Anwendungen

Baut man die natürlichen Zahlen auf den Peano-Axiomen auf, so werden die arithmetischen Grundgesetze wie Assoziativgesetz, Kommutativgesetz und Distributivgesetz für die Addition und Multiplikation natürlicher Zahlen mit vollständiger Induktion bewiesen. Eine ausführliche Ausarbeitung dieser Beweise findet sich in Edmund Landau: Grundlagen der Analysis (Das Rechnen mit ganzen, rationalen, irrationalen, komplexen Zahlen), Leipzig 1930.

Weitere wichtige mathematische Sätze, die üblicherweise mit Induktion bewiesen werden, sind beispielsweise der Binomische Lehrsatz und die Bernoullische Ungleichung.

Verallgemeinerungen und Variationen

Beweis für fast alle natürlichen Zahlen

Der Induktionsbeweis ist auch für Aussagen möglich, die nicht für alle natürlichen Zahlen, sondern nur für alle Zahlen ab einem gewissen Startwert gelten. So lässt sich beispielsweise für die Ungleichung <math>2^n\ge n^2</math> der Induktionsschritt für <math>n\ge 3</math> durchführen:

<math>2^{n+1}=2\cdot 2^n\ge 2n^2</math> laut Induktionsvoraussetzung,

<math>2n^2 =n^2+n^2\ge n^2+3n > n^2+2n+1=(n+1)^2</math> für <math>n\ge 3</math>.

Die Ungleichung ist allerdings für <math>n=3</math> falsch, gilt aber für <math>n=4</math>; der Induktionsbeweis zeigt also die Gültigkeit der Ungleichung für <math>n\ge 4</math>. Die endlich vielen Fälle, die durch den Induktionsbeweis nicht abgedeckt sind, können einzeln untersucht werden.

Verwendung mehrerer Vorgänger

Manchmal ist es notwendig, für den Beweis der Aussage für <math> n+1 </math> die Gültigkeit sowohl für <math> n </math> als auch für <math> n-1 </math> (oder für noch mehr Vorgänger) vorauszusetzen. Der Induktionsanfang muss dann allerdings für mehrere Startwerte (also z.B. <math> n=0 </math> und <math> n=1 </math>) durchgeführt werden, da ja beispielsweise für den Induktionsschritt für <math> n=1 </math> auch die Voraussetzung für <math> n=-1 </math> benötigt würde. Ein Beispiel wäre der Beweis der Formeln von Binet

<math>f_n=\frac{1}{\sqrt{5}}(a^n-b^n)</math> mit a = <math>\frac{1+\sqrt{5}}{2}</math> und b = <math>\frac{1-\sqrt{5}}{2}</math>

für die Fibonacci-Folge <math>f_n</math>.

Vorwärts-rückwärts-Induktion

Eine andere Variante ist die "Vorwärts-rückwärts-Induktion". Dabei wird in einem Vorwärtsschritt die Aussage für beliebig große Zahlen bewiesen, indem z.B. von <math> n </math> auf <math> 2n </math> geschlossen wird. Danach werden die Lücken mit einem Rückwärtsschritt geschlossen, in dem z.B. aus der Gültigkeit für <math> n </math> die Gültigkeit für <math> n-1 </math> bewiesen wird. Diese Technik wurde beispielsweise von Augustin Louis Cauchy, in Cours d'analyse de l'Ecole Royale Polytechnique, premier partie, Analyse algebrique, Paris 1821, S 457ff zum Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet.

Sonstige

Eine andere Verallgemeinerung wäre, als Induktionsvoraussetzung nicht nur eine Aussage für die Zahl <math> n </math> zu verwenden, sondern eine Aussage für alle Zahlen <math> m </math> mit <math> 0 \leq m \leq n </math>. D.h. man darf beim Beweis für <math> n+1 </math> annehmen, dass die Aussage für alle <math> m \leq n </math> gilt. Dies eröffnet der Beweisführung mehr Möglichkeiten.

Aus rechentechnischen Gründen wird oft als Induktionsschritt nicht von <math> n </math> auf <math> n + 1 </math> geschlossen sondern von <math> n - 1 </math> auf <math> n </math>. Dies ist allerdings lediglich eine Notationsänderung, die manchmal die Umformungen vereinfacht, macht aber ansonsten keinen Unterschied.

Wenn man zu allgemeineren Mengen übergehen will, so zeigt sich, dass die vollständige Induktion auf allen Mengen anwendbar ist, auf denen eine partielle Ordnung definiert ist, wobei keine unendlichen absteigenden Ketten auftreten dürfen (weil sonst keine Anfangselemente gefunden werden können). Eine solche Menge heißt fundierte Menge.

Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen können unendlich und größer werden). In diesem Fall wird die Methode transfinite Induktion genannt. Sie ist wichtig in der Mengenlehre und der Topologie.

In der Metamathematik verwendet man eine so genannte unendliche Induktion (auch <math>\omega</math>-Regel genannt). In halbformalen Systemen der Mathematik lassen sich damit Vollständigkeitsbeweise und Widerspruchsfreiheitsbeweise durchführen.

Weblinks

• Cauchy, Augustin-Louis. Analyse algébrique. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel mittels Vorwärts-rückwärts-Induktion ist auf Seite 457ff.
• http://henked.de/begriffe/induktion.htm Vollständige Induktion
• http://www.emath.de/Referate/induktion.pdf Über 100 Aufgaben zur vollständigen Induktion