Induktionsbeweise für Nicht-Mathematiker

Kontext

Was du lernen wirst

In diesem Kapitel lernst du, wie man mit Hilfe der Vollständigen Induktion mathematische Aussagen, anhand einer einfachen Anleitung beweisen kann.

Klausurtipp

Die ersten drei Schritte(Induktionsanfang, -voraussetzung, -behauptung) sind einfach, damit kannst du immer Punkte sammeln.

Was du können solltest

Du solltest wissen wie man Gleichungen umformt(Assoziativgesetz, Distributivgesetz, Kommutativgesetz). Es reichen schon grundlegende Kentnisse aus der Algebra, um diesen Beitrag zu verstehen.

Erklärung

Was ist die vollständige Induktion?

“Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann eine Herleitung nicht für jede Zahl einzeln erbracht werden.”
https://de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion

Nehmen wir an, du möchtest die Aussage beweisen
“Die Summe aller natürlichen Zahlen von $1$ bis $n$ ist $\frac{n(n+1)}{2}$ “.
Dann könnte man als Nicht-Mathematiker sagen “Easy ich setze einfach ‘ne Zahl ein und fertig”. Versuchen wir das doch mal:

für $n$ wählen wir $5$
$1+2+3+4+5 = 15$
$\frac{5(5+1)}{2} = 15$

HA! Bewiesen. Oder?
Aber gilt das auch für alle Zahlen? Oder nur für die 5? Na gut dann setzen wir einfach mal alle Zahlen ein und zwar von 0 bis unendlich. Okay klappt nicht so einfach. Und hier kommt auch schon unser Induktionsbeweis als Beweisverfahren ins Spiel. Denn damit können wir beweisen, dass die Aussage für alle natürlichen Zahlen gilt.

Unser Ziel ist es zu beweisen das die Aussage $A(n)$ für alle $n \epsilon N$ wahr ist.

An dieser Stelle möchte ich noch erwähnen, dass wir die Summe von $1$ bis $n$ , über das Sigma(Summenzeichen) darstellen können. Das würde so aussehen:

$\sum_{i=1}^n i$

Da jedoch nicht jeder an dieser Stelle mit dem Summenzeichen vertraut ist, werde ich darauf in diesem Beitrag verzichten und es in dieser Form schreiben:

$1+2+...+n$

Prinzip der vollständigen Induktion

Die vollständige Induktion funktioniert ungefähr so, wie das Umwerfen von Dominosteinen.
Dabei kannst du dir jeden Stein als konkrete Aussage vorstellen A(1), A(2), A(3).

Die gesamte Reihe der Dominosteine bezeichnet man als Aussageform $A(n)$ .
Damit wir alle Dominosteine umwerfen können, müssen wir zuerst den ersten Dominostein umwerfen. Außerdem müssen die Dominosteine alle hintereinander aufgebaut sein, sodass der zweite Dominostein umfällt, nachdem wir den Ersten umwerfen und dann der Dritte usw.

Der erste Dominostein fällt um wenn wir zeigen können, dass unser Induktionsanfang $A(1)$ gültig ist. Mit Hilfe des Induktionsschritts können wir zeigen, dass auch der darauf folgende Dominostein umfällt.

Kochen mit der vollständigen Induktion!

Wie läuft nun die vollständige Induktion ab?
Tatsächlich können wir uns an einer Anleitung orientieren, ähnlich wie bei einem Kochrezept.
Schau dir zunächst die folgende Übersicht an, anschließend gehe ich auf die Erklärung der einzelnen Schritte ein:

Induktionsanfang(Wir beweisen, dass die Aussage für die kleinste Zahl wahr ist)
Induktionsschritt(Wir beweisen, dass die Aussage auch für alle Zahlen über dem Startwert gilt)
1. Induktionsvoraussetzung formulieren(Wir schreiben aus, dass unsere Annahme für ein $n$ gültig ist)
2. Induktionsbehauptung formulieren(Wir formulieren unser Ziel, und zwar dass wenn es für ein beliebiges $n$ gilt, es auch für das darauf folgende $n+1$ gilt)
3. Beweis des Induktionsschrittes(Unter Verwendung der Voraussetzung formen wir solange um, bis wir die Form der Behauptung erreichen)

Erklärung des Kochrezepts

1. Induktionsanfang

Hier stoßen wir den ersten Dominostein um.
Beim Induktionsanfang ist das Ziel zu zeigen, dass die Aussage für die kleineste erlaubte Zahl gültig ist.
Dafür brauchen wir nur eine kleinste Zahl – in der Regel 1 oder 0 – in unsere Aussage einzusetzen, um herauszufinden, ob die Aussage für diese Zahl gilt.

Zunächst nennen wir die Aussage:

Für alle natürlichen Zahlen $n \geq 1$ gilt:
Die Summe aller natürlichen Zahlen von $1$ bis $n$ ist $\frac{n(n+1)}{2}$ .

Anschließend beginnen wir mit dem eigendlichen Induktionsanfang, indem wir die kleinste Zahl einsetzen.
In unserem Beispiel wäre das die 1, wir können diese einsetzen um zu schauen ob die Aussage für $A(1)$ gilt:

$A(1): 1 = \frac{1(1+1)}{2}$

Wäre diese Aussage an dieser Stelle falsch, dann wären wir bereits fertig. Unsere Aussage hingegen ist gültig.

Wieso nehmen wir nicht einfach irgend eine Zahl als Induktionsanfang?
Der Grund dafür liegt darin, dass wir später mit dem Induktionsschritt, die Aussage für alle Zahlen nach dem Startwert beweisen. Hätten wir den Startwert z.b bei 3, dann hätten wir immer noch nicht die 2,1,0 bewiesen. Daher ist der Startwert in der Regel entweder die 0 oder 1.
Die 0 kann es nur dann sein, wenn wir von den Natürlichen Zahlen mit der 0 sprechen. “In der Regel 0 oder 1” sage ich deshalb, weil es sein kann das die Aussage auch erst ab einer bestimmten Zahl gilt und diese könnte eben größer als 0 bzw. 1 sein. Es gibt aber immer einen kleinsten Startwert.

2. Induktionsvoraussetzung

Ab hier beginnt der Induktionsschritt(bestehend aus Voraussetzung, Behauptung und Beweis), wir möchten zeigen, dass ein umfallender Dominostein den Nächsten auch umwirft.

Die Induktionsvoraussetzung wird häufig auch synonym als Induktionsannahme bezeichnet.

Nachdem wir im Induktionsanfang gezeigt haben, dass die Aussage für ein $n$ gilt, können wir unsere Induktionsvoraussetzung formulieren. Im Grunde ist das etwas redundant, denn wir haben ja bereits im Induktionsanfang gezeigt, dass es gilt. Aber wir sollten das der Richtigkeit halber einmal formulieren, da wir den Rest des Beweises auf dieser Voraussetzung aufbauen. Häufig wird die Voraussetzung und Behauptung auch ganz weggelassen, daher fragt am besten euren Lehrer wie ihr das machen sollt. Dafür kann man einen einfachen Satz formulieren wie:

Die Aussage $A(n)$ gilt für ein beliebiges, aber festes $n$ .
$A(n): 1+2+...+n = \frac{n(n+1)}{2}$

3. Induktionsbehauptung

Bei der Induktionsbehauptung, behaupten wir, dass wenn die Aussage für ein beliebiges $A(n)$ gilt, es auch für $A(n+1)$ gültig ist. Dazu formulieren wir unsere Behauptung und nennen noch die Aussage für $A(n+1)$ . Wir “behaupten” nämlich, dass…

Wenn $A(n)$ gültig ist, dann ist auch $A(n+1)$ gültig.
$A(n+1): 1+2+...+n+(n+1) = \frac{(n+1)((n+1)+ 1)}{2}$

Wir haben in unserer ursprünglichen Aussage das $n$ einfach mit $n+1$ getauscht.

Auch bei der Induktionsbehauptung handelt es sich, um einen Schritt der von vielen weggelassen wird. Wie bereits erwähnt kommt das auf den Lehrer an und was er von dir erwartet.

4. Beweis des Induktionsschritts

Sobald wir bewiesen haben, dass die Aussage für irgend ein beliebiges aber festes $n$ gültig ist und wir unsere Behauptung aufgestellt haben, müssen wir beweisen, dass es auch für die Zahl gültig ist, die darauf folgt, also $A(n+1)$ . Bei unserem Beispiel haben wir bereits gezeigt das die Summe links $1+2+...+n$ das selbe wie $\frac{n(n+1)}{2}$ ist. Wenn wir also zeigen wollen, dass unsere Behauptung gültig ist, dann können wir sie in zwei Teile zerlegen:
$1+2+...+n+ (n+1)$
A(n+1)

1+2+…+n+
A(n)

diese Seite kennen wir bereits:
$\frac{n(n+1)}{2}$

$(n+1)$
Letztes Element von A(n+1)

und diese Seite können wir so lassen.

Setzen wir diese Teile zusammen, können wir sagen:
$1+2+...+n+ (n+1) = \frac{n(n+1)}{2} + (n+1)$

denn wir addieren am Ende den letzten Dominostein noch einmal drauf. Jetzt müssen wir zeigen, dass selbst wenn wir den letzten Dominostein dazu nehmen, die Aussage die gleiche Form hat. Bzw. wir müssen umformen, bis wir die Form aus der Behauptung erhalten. Dafür ist Algebra(leider) nötig. Deswegen scheitern hier viele.

Wir wollen also zeigen dass, über algebraische Umformung zur Behauptung umgeformt werden kann:

$1+2+...+n+ (n+1)$
= …(magic)
= …(more math magic)
$= \frac{(n+1)(n+1)+1}{2}$

$1+2+...+n+ (n+1)$

$= \frac{n(n+1)}{2} + (n+1)$
(Voraussetzung einsetzen)

$= \frac{n(n+1)+2(n+1)}{2}$
(Wir erweitern mit 2 zum addieren der Brüche)

$= \frac{(n+1)(n+2)}{2}$
(Ausklammern von $n+1$ . Die Faktorisierung zu sehen, ist für viele eine Herausforderung. Im Grunde steht im vorhergehenden Schritt einfach $n(x) + 2(x) = x(n+1)$ . Das $n+1$ wäre dann unser ausgeklammertes $x$ )

$= \frac{(n+1)((n+1)+1)}{2}$
(Fertig, wir haben nur eine andere Darstellung von $n+2$ )

Kurz gesagt, im Beweisschritt zerlegen wir unser $A(n+1)$ in zwei Teile, bestehend aus unserer Voraussetzung $A(n)$ und dem darauf folgenden Schritt und führen dann mit Hilfe von Algebra eine Umformung durch, um die Form aus der Behauptung zu erhalten!

Was können wir mit der Vollständigen Induktion alles beweisen?

Leider ist die vollständige Induktion beschränkt auf die natürlichen Zahlen.

Zusammenfassung

Das wichtigste ist es, die 4 Schritte zu kennen:

Induktionsanfang
Induktionsvoraussetzung
Induktionsbehauptung
Beweis des Induktionsschritts

Die Voraussetzung hilft dir beim Beweis(du setzt die Voraussetzung in dem Beweisschritt in der Regel irgendwo ein), die Behauptung ist dein “Ziel”. In diese Form willst du umformen. Der eigendliche Beweis besteht in der Regel aus der Zerlegung deiner Behauptung in die Form aus der Voraussetzung und dem darauf folgenden Schritt. Dafür musst du überlegen woraus deine Aussagenform besteht
( $A(n+1) = A(n) + Letzter Schritt$ ).
$A(n)$ kennst du dank deiner Voraussetzung bereits, also ist an dieser Stelle die Herausforderung den letzten Schritt zu formulieren. Und zum Schluss brauchst du “nur noch” umformen, bis du die Form aus deiner Behauptung erreichst.

Quiz

Induktionsanfang
Induktionsvoraussetzung
Induktionsbehauptung
Beweis des Induktionsschritts

Sie stellt unser Ziel bei der Umformung dar.

Die Induktionsvoraussetzung $A(n)$ können wir in unserem Beweis einsetzen.

Die kleinste mögliche Zahl einsetzen, um zu zeigen, ob die Aussageform für eine beliebig gewählte Zahl gilt.

Übungen

Induktion Aufgaben von Rainer Müller (Mit Lösungsweg)

Empfehlenswerte Beiträge zum Thema