Mathematische Induktion

Die mathematische Induktion ist eine in der Mathematik häufig verwendete Beweismethode, vor allem bei der Arbeit mit natürlichen Zahlen oder einer anderen Folge.

Grundsatz

Das Grundprinzip ist, dass wir eine gegebene Aussage für ein erstes Element beweisen, bei den natürlichen Zahlen ist dies meist n = 1. Wir beweisen dies durch einfache Addition. Im nächsten, induktiven Schritt beweisen wir die Implikation "wenn die Aussage für n = a gilt, dann gilt sie auch für n = a + 1".

Aus diesen beiden Schritten können wir ableiten, dass die Aussage für alle n (aus einer Menge, mit der wir gerade arbeiten) gilt. Warum ist das so? Zu Beginn beweisen wir, dass der Ausdruck für n = 1 gilt. Wir wissen auch, dass der Ausdruck für n = a und n = a + 1 gilt. Also wählen wir a = 1. Wir wissen, dass der Ausdruck für a = 1 gilt, und wir wissen auch, dass er für a + 1 = 2 gilt. An diesem Punkt wissen wir, dass der Ausdruck für a = 2 gilt. Aber da er für a + 1 gilt, muss er auch für 2 + 1 = 3 gelten. Und so weiter.

Das erste Beispiel

Das erste Beispiel wird trivial sein. Wir werden beweisen, dass wir, wenn wir zu einer geraden Zahl zwei addieren, wieder eine gerade Zahl erhalten. Da wir es mit natürlichen Zahlen zu tun haben, schreiben wir eine gerade Zahl im Allgemeinen als 2n, wobei n eine natürliche Zahl ist. Wenn wir nach n eine beliebige natürliche Zahl addieren, erhalten wir im Ergebnis eine gerade Zahl, das ist auf den ersten Blick zu erkennen. Die Teilbarkeit wird mit einem senkrechten Strich wie folgt dargestellt:

$$2\mid2n$$

Diese Schreibweise zeigt an, dass zwei den Ausdruck 2n ohne Rest teilt. Jetzt, da wir die Teilbarkeit schreiben können, können wir schreiben, was wir durch mathematische Induktion beweisen müssen.

$$2\mid 2n+2; \quad n\in\mathbb{N}$$

Das ist es, was wir im ersten Beispiel beweisen sollen, nämlich dass zwei den Ausdruck 2n + 2 teilt - das ist genau das, was das ursprüngliche Wortproblem sagt: "Wenn wir zwei zu einer geraden Zahl addieren, erhalten wir wieder eine gerade Zahl".

Im ersten Schritt der Induktion beweisen wir dies für das erste Element, eins. Wir setzen den Ausdruck n = 1 ein:

$$\begin{eqnarray} 2&\mid& 2\cdot1+2\\ 2&\mid& 4 \end{eqnarray}$$

Zwei dividiert vier ohne Rest, also ist dies für das erste Element wahr. Als nächstes kommt der Induktionsschritt, bei dem wir beweisen müssen, dass, wenn es für das a-te Element gilt, es auch für das (a + 1) -te Element gilt. Zu Beginn nehmen wir an, dass unsere Annahme zutrifft, d.h. n = a:

$$2\mid2a+2$$

Wir nehmen an, dass dieser Ausdruck wahr ist - wir verwenden ihn in der Konstruktion des Beweises. Wir wollen nun beweisen, dass

$$2\mid2(a+1)+2.$$

Was haben wir getan? Anstelle von a haben wir (a + 1) geschrieben. Die Klammern sind wichtig, dieser Ausdruck wäre falsch: 2a + 1 + 2. Wir fügen nicht eine Eins zum ganzen Ausdruck hinzu, sondern machen a wirklich zu einem Ausdruck, der um eins größer ist, also (a + 1). Wir ändern den Ausdruck, indem wir die Klammern multiplizieren.

$$\begin{eqnarray} 2&\mid&2(a+1)+2\\ 2&\mid&2a+2+2
\end{eqnarray}$$

Nun ein kleiner Exkurs zur Teilbarkeit. Wenn wir zwei Zahlen haben, z. B. p und q, die durch eine Zahl, z. B. r, teilbar sind, dann ist ihre Summe auch durch r teilbar. Folglich:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Wir können zum Beispiel die Zahlen p = 8, q = 20 und r = 4 einsetzen. Wir können sehen, dass vier sowohl durch acht als auch durch zwanzig teilbar ist. Das Gleiche gilt für ihre Summe 8 + 20 = 28.

Wie verwenden wir dies in unserem Beispiel? Teilen wir die rechte Seite wie folgt in die Zahlen p und q auf:

$$p=2a+2; \quad q=2$$

Die Zahl q, also zwei, ist trivial durch zwei teilbar. Und der Ausdruck p ist ebenfalls trivial durch zwei teilbar, denn die Prämisse sagt uns das. Der Ausdruck p stimmt genau mit unserer Annahme überein, die wir als wahr annehmen. Und wenn p durch zwei teilbar ist und q durch zwei teilbar ist, dann ist die Summe der beiden durch zwei teilbar.

Noch einmal zu den Annahmen. Wir haben zu Beginn gesagt, dass wir davon ausgehen, dass

$$2\mid2a+2.$$

Wenn wir also bei der Konstruktion des Beweises auf den Ausdruck 2a + 2 stießen, konnten wir sagen, dass er durch zwei teilbar ist. Eben weil es unsere Annahme ist. Dies ist normalerweise der schwierigste Schritt der mathematischen Induktion - zu verstehen, wann und wofür eine induktive Annahme verwendet werden kann.

Damit ist die Induktion beendet, der Beweis ist erfolgreich durchgeführt, das Theorem gilt.

Wenn man wollte, könnte man es anders aufschlüsseln und müsste die Prämisse nicht verwenden. p = 2n und q = 2 + 2. Die Zahl q = 4 ist trivialerweise durch vier teilbar, ebenso wie p = 2n, denn nach der Division durch zwei bleibt n, was natürlich, also ganzzahlig ist. Wir haben also wieder zwei Ausdrücke, die beide durch zwei teilbar sind, also ist auch ihre Summe durch zwei teilbar.

Aber in beiden Fällen haben wir bewiesen, dass

1. der gegebene Ausdruck für n = 1 gilt,

• wenn der Ausdruck für n gilt, dann gilt er auch für n + 1.

Von hier aus können wir bereits ableiten:

• Wir wissen, dass der Ausdruck für n = 1 gilt.
• Wenn er für n gilt, muss er auch für n + 1 gelten, d.h. auch für 1 + 1, d.h. der Ausdruck gilt auch für n = 2.
• Wenn er für n gilt, muss er auch für n + 1 gelten, d. h. auch für 2 + 1, d. h. der Ausdruck gilt auch für n = 3.
• Wenn er für n gilt, muss er auch für n + 1 gelten, d. h. auch für 3 + 1, d. h. der Ausdruck gilt für n = 4.
• Wenn er für n gilt, muss er auch für n + 1 gelten, d. h. auch für 4 + 1, d. h. der Ausdruck gilt für n = 5.
• ...

Zweites Beispiel

Als nächstes beweisen wir eine einfache Aussage durch mathematische Induktion:

$$2^n\ge2n;\quad n\in\mathbb{N}.$$

Im ersten Schritt finden wir heraus, ob die Aussage für n = 1 gilt, als erstes Element der natürlichen Zahlen, aus denen n ausgewählt wird.

$$\begin{eqnarray} 2^1&\ge&2\cdot1\\ 2&\ge&2 \end{eqnarray}$$

Sie gilt trivialerweise. Nun gehen wir zum Induktionsschritt über, in dem wir sehen müssen, ob sie für n = a gilt, wenn sie auch für n = a + 1 gilt. Unsere Annahme ist also, dass sie gilt

$$2^a\ge2a$$

und das wollen wir beweisen:

$$2^{a+1}\ge2(a+1)$$

Wir zerlegen zunächst die linke Seite nach den Regeln der Potenzrechnung und multiplizieren einfach die rechte Seite.

$$2\cdot2^a\ge2a+2$$

Auf der linken Seite verwenden wir die Addition statt der Multiplikation und lassen die rechte Seite unverändert.

$$2^a+2^a\ge2a+2$$

Jetzt werden wir die Annahme verwenden. Eine Vermutung ist eine Aussage, von der wir annehmen, dass sie wahr ist. In der Ungleichung haben wir zwei Ausdrücke auf jeder Seite, die sich addieren. Gleichzeitig wissen wir, dass

$$\begin{eqnarray} 2^a&\ge&2a\\ 2^a&\ge&2. \end{eqnarray}$$

Die erste Zeile sagt uns die Annahme und die zweite Aussage ist trivial (die niedrigste 2^a ist für a = 1 und sie ist gleich zwei). Wir wissen also, dass die beiden Ausdrücke auf der linken Seite größer als oder gleich den beiden Ausdrücken auf der rechten Seite sind. Wir haben also durch Induktion bewiesen, dass, wenn ein Ausdruck für a wahr ist, er auch für (a + 1) wahr ist, und da der Ausdruck für eins wahr ist, ist der Ausdruck auch wahr.

Das dritte Beispiel

Versuchen wir, die folgende Aussage zu beweisen:

$$3\mid n\Rightarrow 3\mid n^2;\quad n\in\mathbb{N}$$

Verbal: Wenn n durch drei teilbar ist, dann ist auch n² durch drei teilbar. Wenn n nicht durch drei teilbar ist, dann ist der Ausdruck trivialerweise wahr (durch die Definition der Implikation), also werden wir die Fälle betrachten, in denen n durch drei teilbar ist. Dies erzeugt eine Folge von natürlichen Zahlen a_i=3, 6, 9, 12, 15... Von nun an werden wir uns durch diese Folge a_i bewegen.

Wir beginnen den Beweis durch Induktion mit dem ersten Schritt, d.h. wenn er für das erste Element gilt. Wir erinnern uns, dass wir uns in der Folge a_i bewegen, also nehmen wir das erste Element dieser Folge, d.h. das Element a₁, das eine Drei ist. Für drei ist der Ausdruck gültig:

$$3\mid3\Rightarrow 3\mid3^2$$

Wir gehen nun zum Induktionsschritt über. Wir sehen, dass die Folge a_i als 3n geschrieben werden kann, wobei n eine natürliche Zahl ist. Somit ist das zweite Element um drei größer als das vorherige usw. Nehmen wir nun an, dass der Ausdruck für n gilt, und wir müssen sicherstellen, dass er auch für (n + 3) gilt, was eine Vorschrift ist, die das nächste Element in der Folge erzeugt, durch die wir uns bewegen. Lassen Sie uns zuerst die Annahme aufschreiben:

$$3\mid n\Rightarrow 3\mid n^2$$

und dann, was wir beweisen wollen

$$3\mid (n+3)\Rightarrow 3\mid(n+3)^2.$$

Wir zerlegen die Klammer auf der anderen Seite mit Hilfe der Formel:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Und wir sind fast am Ziel. Auf der linken Seite haben wir einen Ausdruck, der definitiv durch drei teilbar ist, denn n ist durch drei teilbar (wir bewegen uns nur in den Zahlen der Folge a_i), und drei ist auch durch drei teilbar. Auf der rechten Seite haben wir zunächst n², die durch drei teilbar ist. Das heißt, wir wissen, dass n durch drei teilbar ist, und die Annahme besagt, dass wenn n durch drei teilbar ist, dann ist auch n² durch drei teilbar:

$$3\mid n\Rightarrow 3\mid n^2$$

Dann folgt der Ausdruck 6n, der trivialerweise durch drei teilbar ist. Man kann ihn sich als eine Kontraktion eines Bruchs vorstellen:

$$\frac{6n}{3}=2n$$

Die Variable n ist eine natürliche Zahl, also ist auch das Produkt 2n eine natürliche Zahl, d.h. nach der Division durch drei haben wir eine natürliche Zahl, und somit muss der Ausdruck 6n durch drei teilbar sein. Und die Neun am Ende ist wiederum durch drei teilbar. Der Ausdruck gilt für das erste Element und für den Induktionsschritt, also ist er wahr.

Die Anzahl der Klammern im Ausdruck

Das letzte Beispiel ist ein wenig untypisch. Wir wollen versuchen, die Behauptung zu beweisen, dass die Anzahl der Klammern in einem einfachen Ausdruck immer gerade ist, damit Sie sehen, dass die mathematische Induktion in einem ganz anderen Zusammenhang als nur mit natürlichen Zahlen verwendet werden kann. Zu Beginn müssen wir definieren, was ein einfacher Ausdruck ist. Ein einfacher Ausdruck ist:

• eine natürliche Zahl,
• Wenn p ein einfacher Ausdruck ist, dann ist (p²) ein einfacher Ausdruck,
• wenn p und q einfache Ausdrücke sind, dann ist (p + q) ein einfacher Ausdruck.

Was ist also ein einfacher Ausdruck: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Umgekehrt sind dies keine einfachen Ausdrücke:

• 1 + 2 $\rightarrow$ Es fehlen die äußeren Klammern,
• (1 + 2 $\rightarrow$ fehlende rechte Klammern,
• 13² $\rightarrow$ fehlende äußere Klammern,
• (1 + 2 + 3) $\rightarrow$ fehlende Klammern, die korrekte Schreibweise müsste lauten (1+(2 + 3))

Ein einfacher Ausdruck kann zum Beispiel wie folgt gebildet werden. Am Anfang wählen wir den einfachen Ausdruck (a + b). Nach a fügen wir den einfachen Ausdruck a = (c + d) ein, so dass wir ((c + d)+b) erhalten, und nach b fügen wir ein Tripel ein: ((c + d)+3) Nach c fügen wir eine Zehn ein: ((10 + d)+3) und schließlich nach d setzen wir (5²) ein: ((10+(5²))+3) Es ist wichtig, die Klammern zu beachten, sonst wird es nicht funktionieren.

Nun beweisen wir, dass der einfache Ausdruck eine gerade Anzahl von Klammern enthält (gerade Zahlen schließen Null ein).

Im ersten Schritt der Induktion wählen wir ein erstes Element. In diesem Fall wird das erste Element der trivialste einfache Ausdruck sein, also eine beliebige natürliche Zahl. Wir setzen also

$$j=n;\quad n\in\mathbb{N}.$$

Für den Ausdruck j ist die Anzahl der Klammern gleich Null, so dass das erste Element erfüllt ist. Im Induktionsschritt nehmen wir an, dass wir zwei einfache Ausdrücke p und q haben und dass sie beide eine gerade Anzahl von Klammern haben. Dann müssen wir beweisen, dass die einfachen Ausdrücke (p + q) und (p²) ebenfalls eine gerade Anzahl von Klammern haben.

Zuerst die Addition. Wir definieren eine weitere Funktion z(q), die die Anzahl der Klammern des Ausdrucks q zurückgibt. Dann hat der Ausdruck (p + q) z(p)+z(q)+2 Klammern. Das heißt, er hat zwei Klammern mehr als die Summe der Klammern der Ausdrücke p und q. Da z(p) und z(q) beide gerade sind, erhalten wir bei der Addition von drei geraden Zahlen wieder eine gerade Zahl. Für diesen Fall gilt die Aussage.

Nun zur Potenz. Wieder gilt die Annahme, dass der einfache Ausdruck p eine gerade Anzahl von Klammern enthält. Der Ausdruck (p²) enthält dann z(p)+2 Klammern, also wieder zwei Klammern mehr als der Ausdruck p. Auch in diesem Fall addieren wir gerade Zahlen, also ist das Ergebnis gerade.

Die Aussage ist wahr für das erste Element und ist auch im Induktionsschritt wahr, also ist die Aussage wahr.

Weitere Ressourcen und Beispiele

• Viele Beispiele im Matheforum
• Folien auf fi.muni.cz [PDF]