Vollständige Induktion

Die vollständige Induktion ist eine in der Mathematik häufig verwendete Beweismethode, meistens wenn wir mit natürlichen Zahlen oder mit einer anderen Folge arbeiten.

Prinzip

Das Grundprinzip besteht darin, dass wir die Aussage für ein erstes Element beweisen, bei den natürlichen Zahlen ist das meistens n = 1. Das beweisen wir durch einfaches Einsetzen. Im weiteren Schritt, dem Induktionsschritt, 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 folgern, dass die Aussage für alle n gilt (aus irgendeiner Menge, mit der wir gerade arbeiten). Warum ist das so? Am Anfang beweisen wir, dass die Aussage für n = 1 gilt. Gleichzeitig wissen wir, dass die Aussage für n = a + 1 gilt, wenn sie für n = a gilt. Wir wählen also a = 1. Wir wissen, dass die Aussage für a = 1 gilt, und wir wissen auch, dass sie für a + 1 = 2 gilt. Jetzt wissen wir also, dass die Aussage für a = 2 gilt. Weil sie aber auch für a + 1 gilt, muss sie auch für 2 + 1 = 3 gelten. Und so weiter.

Erstes Beispiel

Das erste Beispiel ist trivial. Wir beweisen, dass wir wieder eine gerade Zahl erhalten, wenn wir zu einer beliebigen geraden Zahl zwei addieren. Weil wir uns in den natürlichen Zahlen bewegen, schreiben wir eine allgemeine gerade Zahl als 2n, wobei n eine natürliche Zahl ist. Wenn wir für n eine beliebige natürliche Zahl einsetzen, erhalten wir als Ergebnis eine gerade Zahl, das sieht man auf den ersten Blick. Die Teilbarkeit schreibt man mit einem senkrechten Strich so:

$$2\mid 2n$$

Diese Schreibweise bedeutet, dass die Zwei den Term 2n ohne Rest teilt. Wenn wir die Teilbarkeit schon aufschreiben können, können wir auch das aufschreiben, was wir durch vollständige Induktion beweisen wollen.

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

Das sollen wir im ersten Beispiel beweisen, also dass die Zwei den Term 2n + 2 teilt – genau das entspricht der ursprünglichen Aufgabe in Worten „Wenn wir zu einer beliebigen geraden Zahl zwei addieren, erhalten wir wieder eine gerade Zahl“.

Im Induktionsanfang beweisen wir es für das erste Element, für die Eins. Wir setzen in den Term n = 1 ein:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Die Zwei teilt die Vier ohne Rest, also gilt es für das erste Element. Nun folgt der Induktionsschritt, in dem wir beweisen müssen: Wenn es für das a-te Element gilt, dann gilt es auch für das (a + 1)-te Element. Am Anfang nehmen wir an, dass unsere Voraussetzung gilt, d. h. n = a:

$$2\mid 2a+2$$

Von diesem Term nehmen wir an, dass er wahr ist – wir verwenden ihn beim Aufbau des Beweises. Wir wollen nun beweisen, dass

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

Was haben wir gemacht? Anstelle von a haben wir (a + 1) geschrieben. Die Klammern sind wichtig, dieser Term wäre falsch: 2a + 1 + 2. Wir addieren nicht eins zum ganzen Term, sondern machen wirklich aus a einen um eins größeren Ausdruck, d. h. (a + 1). Den Term formen wir um, indem wir die Klammer ausmultiplizieren.

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

Nun ein kleiner Exkurs zur Teilbarkeit. Wenn wir zwei Zahlen haben, sagen wir p und q, die durch eine Zahl teilbar sind, etwa r, dann gilt, dass auch ihre Summe durch r teilbar ist. Es gilt also:

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

Wir können dort zum Beispiel die Zahlen p = 8, q = 20 und r = 4 einsetzen. Wir sehen, dass die Vier sowohl die Acht als auch die Zwanzig teilt. Und genauso teilt sie auch ihre Summe 8 + 20 = 28.

Wie nutzen wir das in unserem Beispiel? Wir teilen die rechte Seite so in die Zahlen p und q auf:

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

Die Zahl q, also die Zwei, ist trivialerweise durch zwei teilbar. Und der Term p ist ebenfalls durch zwei teilbar, weil uns das die Voraussetzung sagt. Der Term p entspricht genau unserer Voraussetzung, von der wir annehmen, dass sie wahr ist. Und wenn p durch zwei teilbar ist und zugleich q durch zwei teilbar ist, dann ist auch ihre Summe durch zwei teilbar.

Noch einmal zur Voraussetzung. Am Anfang haben wir gesagt, dass wir annehmen, dass

$$2\mid 2a+2$$

gilt. Wenn wir also beim Aufbau des Beweises auf den Term 2a + 2 gestoßen sind, konnten wir von ihm sagen, dass er durch zwei teilbar ist. Genau deshalb, weil es unsere Voraussetzung ist. Das ist gewöhnlich der schwierigste Schritt der vollständigen Induktion – zu verstehen, wann und warum man die Induktionsvoraussetzung verwenden darf.

Damit endet die Induktion, der Beweis wurde erfolgreich geführt, der Satz gilt.

Wenn du möchtest, könntest du es auch anders zerlegen und müsstest die Voraussetzung nicht verwenden. p = 2n und q = 2 + 2. Die Zahl q = 4 ist trivialerweise durch zwei teilbar und ebenso p = 2n, weil nach der Division durch zwei die Zahl n übrig bleibt, die natürlich, d. h. ganz ist. Wieder haben wir zwei Terme erhalten, die beide durch zwei teilbar sind, also ist auch ihre Summe durch zwei teilbar.

In beiden Fällen haben wir aber bewiesen, dass

1. die Aussage für n = 1 gilt,
2. wenn die Aussage für n gilt, dann gilt sie auch für n + 1.

Daraus können wir nun folgern:

• Wir wissen, dass die Aussage für n = 1 gilt.
• Wenn sie für n gilt, muss sie auch für n + 1 gelten, d. h. auch für 1 + 1, d. h. die Aussage gilt auch für n = 2.
• Wenn sie für n gilt, muss sie auch für n + 1 gelten, d. h. auch für 2 + 1, d. h. die Aussage gilt auch für n = 3.
• Wenn sie für n gilt, muss sie auch für n + 1 gelten, d. h. auch für 3 + 1, d. h. die Aussage gilt auch für n = 4.
• Wenn sie für n gilt, muss sie auch für n + 1 gelten, d. h. auch für 4 + 1, d. h. die Aussage gilt auch für n = 5.
• …

Zweites Beispiel

Als Nächstes beweisen wir durch vollständige Induktion eine einfache Aussage:

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

Zuerst der Induktionsanfang: Wir prüfen, ob die Aussage für n = 1 gilt, als erstes Element der natürlichen Zahlen, aus denen wir n wählen.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Das gilt trivialerweise. Nun gehen wir zum Induktionsschritt über, in dem wir herausfinden müssen, ob die Aussage für n = a + 1 gilt, wenn sie für n = a gilt. Unsere Voraussetzung ist also, dass

$$2^a\ge 2a$$

gilt, und wir wollen beweisen:

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

Die linke Seite schreiben wir zuerst mithilfe der Regeln für das Rechnen mit Potenzen um und die rechte Seite multiplizieren wir einfach aus.

$$2\cdot 2^a\ge 2a+2$$

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

$$2^a+2^a\ge 2a+2$$

Nun nutzen wir die Voraussetzung. Die Voraussetzung ist eine Aussage, von der wir annehmen, dass sie gilt. In der Ungleichung haben wir auf beiden Seiten je zwei Terme, die addiert werden. Gleichzeitig wissen wir aber, dass

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

Die erste Zeile sagt uns die Voraussetzung und die zweite Aussage ist trivial (der kleinste Wert von 2^a ist für a = 1 und der ist genau zwei). Wir wissen also, dass auf der linken Seite beide Terme größer oder gleich den beiden Termen auf der rechten Seite sind. Damit haben wir durch Induktion bewiesen, dass die Aussage für (a + 1) gilt, wenn sie für a gilt, und weil die Aussage auch für die Eins gilt, ist sie wahr.

Drittes Beispiel

Wir versuchen, die folgende Aussage zu beweisen:

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

In Worten: Wenn n durch drei teilbar ist, dann ist auch n² durch drei teilbar. Wenn n nicht durch drei teilbar ist, dann gilt die Aussage trivialerweise (aus der Definition der Implikation), also beschäftigen wir uns mit den Fällen, in denen n durch drei teilbar ist. Das ergibt eine Folge natürlicher Zahlen a_i=3, 6, 9, 12, 15… Von nun an bewegen wir uns in dieser Folge a_i.

Den Induktionsbeweis beginnen wir mit dem Induktionsanfang, d. h. ob es für das erste Element gilt. Ich erinnere daran, dass wir uns in der Folge a_i bewegen, also nehmen wir das erste Element dieser Folge, d. h. das Element a₁, das ist die Drei. Für die Drei gilt die Aussage:

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

Nun gehen wir zum Induktionsschritt über. Wir sehen, dass sich die Folge a_i als 3n schreiben ließe, wobei n eine natürliche Zahl ist. Das zweite Element ist also um drei größer als das vorherige usw. Nehmen wir nun an, dass die Aussage für n gilt; wir müssen sicherstellen, dass sie auch für (n + 3) gilt, das ist die Vorschrift, die das nächste Element der Folge erzeugt, in der wir uns bewegen. Wir schreiben zuerst die Voraussetzung auf:

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

und dann das, was wir beweisen wollen

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

Die Klammer auf der anderen Seite lösen wir mithilfe der Formel auf:

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

Und schon sind wir fast am Ziel. Auf der linken Seite haben wir einen Term, der sicher durch drei teilbar ist, weil n laut Voraussetzung durch drei teilbar ist (wir bewegen uns nur in den Zahlen aus der Folge a_i) und die Drei ebenfalls durch drei teilbar ist. Auf der rechten Seite haben wir zuerst n², das laut Voraussetzung durch drei teilbar ist. Wir wissen nämlich, dass n durch drei teilbar ist, und die Voraussetzung sagt, dass n² durch drei teilbar ist, wenn n durch drei teilbar ist:

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

Weiter folgt der Term 6n, der trivialerweise durch drei teilbar ist. Du kannst dir das als Kürzen eines Bruchs vorstellen:

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

Die Variable n ist irgendeine 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 erhalten und der Term 6n muss somit durch drei teilbar sein. Und die Neun am Ende ist wieder durch drei teilbar. Die Aussage gilt für das erste Element und im Induktionsschritt, ist also wahr.

Anzahl der Klammern in einem Term

Das letzte Beispiel ist etwas untypisch. Wir versuchen die Aussage zu beweisen, dass die Anzahl der Klammern in einem einfachen Term immer gerade ist, damit du siehst, dass sich die vollständige Induktion auch in einem ganz anderen Zusammenhang als nur bei den natürlichen Zahlen verwenden lässt. Am Anfang müssen wir definieren, was ein einfacher Term ist. Ein einfacher Term ist:

• eine natürliche Zahl,
• wenn p ein einfacher Term ist, dann ist auch (p²) ein einfacher Term,
• wenn p und q einfache Terme sind, dann ist auch (p + q) ein einfacher Term.

Einfache Terme sind also zum Beispiel: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Und dies sind dagegen keine einfachen Terme:

• 1 + 2 → die äußeren Klammern fehlen,
• (1 + 2 → die rechte Klammer fehlt,
• 13² → die äußeren Klammern fehlen,
• (1 + 2 + 3) → Klammern fehlen, richtig müsste die Schreibweise (1 + (2 + 3)) lauten

Ein einfacher Term kann zum Beispiel so entstehen. Am Anfang wählen wir den einfachen Term (a + b). Nun setzen wir für a den einfachen Term a = (c + d) ein, also erhalten wir ((c + d) + b), und für b setzen wir die Drei ein: ((c + d) + 3). Für c setzen wir die Zehn ein: ((10 + d) + 3) und schließlich für d setzen wir (5²) ein: ((10 + (5²)) + 3). Es ist wichtig, die Klammern einzuhalten, sonst funktioniert es nicht.

Nun beweisen wir, dass ein einfacher Term eine gerade Anzahl von Klammern enthält (zu den geraden Zahlen gehört auch die Null).

Im Induktionsanfang wählen wir irgendein erstes Element. In diesem Fall ist das erste Element der trivialste einfache Term, nämlich eine beliebige natürliche Zahl. Wir setzen also

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

Für den Term j gilt, dass die Anzahl der Klammern null ist, das erste Element erfüllt die Aussage also. Im Induktionsschritt nehmen wir an, dass wir zwei einfache Terme p und q haben und dass beide eine gerade Anzahl von Klammern haben. Dann müssen wir beweisen, dass auch die einfachen Terme (p + q) und (p²) eine gerade Anzahl von Klammern haben.

Zuerst die Addition. Wir definieren noch eine Funktion z(q), die die Anzahl der Klammern des Terms q zurückgibt. Dann gilt, dass der Term (p + q) genau z(p) + z(q) + 2 Klammern hat. Er hat also zwei Klammern mehr als die Summe der Klammern der Terme p und q. Laut Voraussetzung sind z(p) und z(q) gerade, wenn wir also drei gerade Zahlen addieren, erhalten wir wieder eine gerade Zahl. Für diesen Fall gilt die Aussage.

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

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