Mathe-Artikel: Vollständige Induktion

Question

Die vollständige Induktion ist ein Beweisverfahren, das angewendet wird, um zu beweisen, dass eine Aussage, die von einer natürlichen Zahl abhängt, für alle $n \ge n_o$ gilt, wobei $n_0 \in \mathbb{N}_0$. Wir schreiben $A(n)$ für unsere Aussage in Abhängigkeit von $n \in \mathbb{N}_0$.

Vorgehensweise:

1.) Induktionsanker/Induktionsanfang (kurz: IA):

Im Induktionsanker zeigen wir, dass $A(n_0)$ wahr ist, wobei wir $n_0 \in \mathbb{N_0}$ so klein wie möglich wählen. Meistens ist dies die Zahl 0 oder 1.

2.) Induktionsvoraussetzung (kurz: IV):

Hier setzen wir voraus, dass $A(n)$ für ein festes, aber beliebiges $n \in N$ gilt, wobei $N :=\{m \in \mathbb{N} \ \vert \ m \ge n_0\}$. Meist schreiben wir sowas wie: „Für ein festes, aber beliebiges $n \in N$ gilt: $A(n)$“, wobei wir für $A(n)$ die Aussage hinschreiben.

Achtung:

Ein häufiger Fehler hierbei ist die folgende Formulierung: „Für $n \in N$ gilt: $A(n)$“

Dort wird vorausgesetzt, dass unsere Aussage für alle $n \in N$ wahr ist, womit wir uns die Induktion sparen könnten. Wir setzen in der Induktionsvoraussetzung lediglich voraus, dass ein $n \in N$ die Aussage erfüllt!

3.) Induktionsschritt/Induktionsschluss (kurz: IS)

Im dritten und letzten Schritt findet die eigentliche Arbeit der Induktion statt. Wir möchten hier zeigen, dass, wenn die Aussage für unser festes, aber beliebiges $n \in N$ wahr ist, sie auch für $n+1$ gilt.

Kurz: $A(n) \Rightarrow A(n+1)$

Manchmal (aber selten) kommt es auch vor, dass wir zusätzlich den Induktionsanker verwenden können.

Zusammenfassung der Schritte:

Wir zeigen, dass $A(n)$ für ein $n_0 \in \mathbb{N}_0$ gilt (IA), setzen voraus, dass die Aussage für ein festes, aber beliebiges $n \in N$ wahr ist (IV), um letztendlich im Induktionsschritt (IS) zu zeigen, dass die Eigenschaft der Aussage dann auch für $n+1$ erfüllt ist. Somit ist $A(n)$ für alle $n \ge n_0$ wahr.

Idee „anschaulich“: $\underbrace{A(n_0)}_{IA} \overset{IS}{\Rightarrow} A(n_0+1) \overset{IS}{\Rightarrow} A(n_0+2) \overset{IS}{\Rightarrow} \ldots$

Damit die Vorgehensweise klarer wird, wird die Induktion an einem Beispiel erläutert.

Beispiel: Gaußsche Summenformel

Das wohl typischste Beispiel für die Anwendung der vollständigen Induktion ist die Gaußsche Summenformel, womit an dieser Stelle die Geschichte des kleinen Gauß erwähnt sei:

Der kleine Gauß sitzt mit seinen Mitschülern/Mitschülerinnen im Mathematikunterricht. Sie bekommen von ihre Lehrer folgende Aufgabe gestellt: „Berechnet die Summe der Zahlen von 1 bis 100!“

Der Lehrer, stark im Glauben er könne sich nun eine lange Auszeit gönnen, lehnt sich zurück und lässt die Schüler/innen rechnen. Alle beginnen die Zahlen mühsam zu addieren und schreiben ihre Zwischenschritte auf Schreibtafeln. Alle? Nein! Der kleine Gauß sitzt ruhig auf seinem Stuhl und denkt nach:

$$\begin{aligned} 1+100&=101 \\ 2+99 &= 101 \\ 3+98 &=101 \\ \quad &\vdots \\ 49+52 &=101 \\ 50+51 &=101 \end{aligned}$$

Er stellt fest, dass er durch schlaues Addieren der Summanden 50-mal die Zahl 101 erhält.

Es gilt:

$$\overset{100}{\underset{k=1}{\sum}} k = 50 \cdot 101 =5050$$

Natürlich kann man solch eine Summe nicht nur geschickt von 1 bis 100 ausrechnen, sondern bis zu einem beliebigen $n \in \mathbb{N}$.

Es gilt:

$$\overset{n}{\underset{k=1}{\sum}}k= \frac{n \cdot (n+1)}{2}$$
Diese Aussage bezeichnen wir mit $A(n)$.

Wir überprüfen, ob $A(n)$ tatsächlich für $n=100$ gilt:

$$\overset{100}{\underset{k=1}{\sum}}k= \frac{100 \cdot 101}{2}=\frac{50 \cdot 101}{1}=5050$$

Woher wissen wir aber nun, dass dies nicht nur Zufall war? Ein Glücktreffer. Es könnte ja sein, dass die Aussage für $n=100$ gilt, jedoch für $n=101$ nicht. An dieser Stelle kommt die vollständige Induktion ins Spiel! Mit ihrer Hilfe beweisen wir, dass $A(n)$ für alle natürlichen Zahlen $n$ gilt.

Beweis:

Induktionsanker:

Sei $n_0=1$.

Es gilt:

$$\overset{1}{\underset{k=1}{\sum}}k = 1 = \frac{1 \cdot (1+1)}{1}$$

Induktionsvoraussetzung:

Für ein festes, aber beliebiges $n \in \mathbb{N}$ gilt:

$$\overset{n}{\underset{k=1}{\sum}}k= \frac{n \cdot (n+1)}{2}$$

Induktionsschritt:

$$\begin{aligned} \overset{n+1}{\underset{k=1}{\sum}}k &= \overset{n}{\underset{k=1}{\sum}}k+(n+1) \\ &\overset{IV}{=} \frac{n \cdot (n+1)}{2} + (n+1) \\ &= \frac{n \cdot (n+1)}{2} + \frac{2 \cdot (n+1)}{2} \\ &= \frac{n \cdot (n+1)+2 \cdot (n+1)}{2} \\ &=\frac{(n+2) \cdot (n+1)}{2} \\ &= \frac{(n+1) \cdot ((n+1)+1)}{2} \end{aligned}$$

Wir haben nun in wenigen Schritten gezeigt, dass $A(n)$ für alle natürlichen Zahlen $n$ gilt.


Wieso funktioniert die vollständige Induktion als Beweisverfahren überhaupt? Um diese Frage zu beantworten, beweisen wir folgende Aussage:

Gilt eine Aussage $A(n_0)$ für ein $n_0 \in \mathbb{N}_0$ und folgt aus der wahren Aussage $A(n)$ mit $n \in N$, dass $A(n+1)$ ebenfalls gilt, so ist $A(n)$ für alle $n \in N$ wahr.

Beweis:
Addieren wir zu einem $n_0 \in \mathbb{N}_0$ eine $1$, so erhalten wir die darauffolgende natürliche Zahl $n_0+1$. Wir können jede beliebig große natürliche Zahl $n \ge n_0$ erhalten indem wir entsprechend oft eine $1$ addieren. Dies wird als Prinzip der vollständigen Induktion bezeichnet.

Nun wissen wir, dass $A(n_0)$ für ein $n_0 \in \mathbb{N}_0$ und $„A(n) \ \text{wahr} \ \Rightarrow A(n+1) \ \text{wahr}“$ gilt. Um zu beweisen, dass die Aussage für eine beliebige natürliche Zahl aus $N$ gilt, müssen wir also $„A(n) \ \text{wahr} \ \Rightarrow A(n+1) \ \text{wahr}“$ entsprechend oft anwenden.
Somit gilt $A(n)$ für alle $n \in N$.


Beispiele für weitere Gleichungen, die mit Hilfe der vollständigen Induktion bewiesen werden können:

1.) Für $n \in \mathbb{N}$ gilt:

$$\overset{n}{\underset{k=1}{\sum}}k^2 = \frac{n \cdot (n+1) \cdot (2n+1)}{6}$$

2.) Für $n \in \mathbb{N}$ gilt der binomische Lehrsatz:

$$(x+y)^n=\overset{n}{\underset{k=1}{\sum}} \binom{n}{k} \cdot x^{n-k} \cdot y^k$$

Comments

Hiermit stelle ich euch mal meinen ersten Artikel vor. Es wurde bereits drüber geschaut, jedoch können sich hier und da natürlich Fehler eingeschlichen haben, welche ihr mir gerne mitteilen könnt. 

Über Feedback würde ich mich freuen! :)

---

Das ist eigentlich ein Kochrezept. Meines Erachtens fehlt da eine Einleitung, die begruendet, warum vollstaendige Induktion ueberhaupt funktioniert und ein Beweisverfahren sein soll. Denn genau das (so befuerchte ich) haben die wenigsten je kapiert.

---

Ich fände es wichtig, dass da noch sowas vorkommt wie:

Eine Aussage, die für alle natürlichen Zahlen gilt.

bzw. die für alle natürlichen Zahlen, die größer gleich n₀ sind, gilt.

---

Ich kenne die Geschichte, dass Gauss wie folgt zusammengefasst hatte

1 + 100 = 101

2 + 99 = 101

3 + 98 = 101

...

50 + 51 = 101

Also

50 * 101 = 5050

Wenn man die Summe von 100 aufeinanderfolgende Zahlen bilden soll kann man diese zu 50 Pärchen zusammenfassen, die alle den denselben Wert haben.

---

Eine sehr schöne Erklärung der vollständigen Induktion kommt von dem Mathedidakt Christian Spannagel 

---

Danke für euer Feedback!

@Fakename:

Ein kleiner Beweis würde wirklich nicht schaden.

Wir haben nun in wenigen Schritten gezeigt, dass $A(n)$ für alle natürlichen Zahlen $n$ gilt.

Wieso funktioniert die vollständige Induktion als Beweisverfahren überhaupt? Um diese Frage zu beantworten, beweisen wir folgende Aussage:

Gilt eine Aussage $A(n_0)$ für ein $n_0 \in \mathbb{N}_0$ und folgt aus der wahren Aussage $A(n)$ mit $n \in N$, dass $A(n+1)$ ebenfalls gilt, so ist $A(n)$ für alle $n \in N$ wahr.

Beweis:
Addieren wir zu einem $n_0 \in \mathbb{N}_0$ eine $1$, so erhalten wir die darauffolgende natürliche Zahl $n_0+1$. Wir können jede beliebig große natürliche Zahl $n \ge n_0$ erhalten indem wir entsprechend oft eine $1$ addieren. Dies wird als Prinzip der vollständigen Induktion bezeichnet.

Nun wissen wir, dass $A(n_0)$ für ein $n_0 \in \mathbb{N}_0$ und $„A(n) \ \text{wahr} \ \Rightarrow A(n+1) \ \text{wahr}“$ gilt. Um zu beweisen, dass die Aussage für eine beliebige natürliche Zahl aus $N$ gilt, müssen wir also $„A(n) \ \text{wahr} \ \Rightarrow A(n+1) \ \text{wahr}“$ entsprechend oft anwenden. 
Somit gilt $A(n)$ für alle $n \in N$.

Beispiele für weitere Gleichungen, die mit Hilfe der vollständigen Induktion bewiesen werden können:

@mathef:

Stimmt, das hätte ich besser formulieren können.

Die vollständige Induktion ist ein Beweisverfahren, das angewendet wird, um zu beweisen, dass eine Aussage, die von einer natürlichen Zahl abhängt, für alle $n \ge n_o$ gilt, wobei $n_0 \in \mathbb{N}_0$. Wir schreiben $A(n)$ für unsere Aussage in Abhängigkeit von $n \in \mathbb{N}_0$.

@Mathecoach:

Ich hatte es mit 100 im Kopf, mein Fehler. Mit 101 ist es offensichtlich schöner.

$$\begin{aligned} 1+100&=101 \\ 2+99 &= 101 \\ 3+98 &=101 \\ \quad &\vdots \\ 49+52 &=101 \\ 50+51 &=101 \end{aligned}$$

Er stellt fest, dass er durch schlaues Addieren der Summanden 50-mal die Zahl 101 erhält.

Es gilt:

$$\overset{100}{\underset{k=1}{\sum}} k = 50 \cdot 101 =5050$$

@Alle:

Wäre es möglich, dass jemand die entsprechenden Textstellen durch die grün hervorgehobenen ersetzt? (Natürlich soll die Ersetzung nicht in grün sein, das dient nur zur Hervorhebung :) )

Den Beweis, dass die vollständige Induktion ein korrektes Beweisverfahren ist, würde ich gerne fast ans Ende des Artikels packen (erste und letzter Satz zeigen im grün hervorgehobenen zeigen wo genau). Wäre der Beweis mitten drin, so kann ich mir vorstellen, dass das Schüler/innen, die gar keine Beweise in der Schule behandeln, verwirrt. Zur Vollständigkeit ist es aber doch nicht verkehrt in dabei zu packen.

Bei dem rot markieren bin ich mir nicht sicher, ob das in Ordnung geht, da wir in der Uni die vollständige Induktion mit $n_0=0$ eingeführt haben und das Prinzip der vollständigen Induktion "Addiert man zu der Zahl 0 sukzessiv die Zahl 1, so erhält man nach und nach alle natürlichen Zahlen." lautete. Ich mache ja nichts anderes, nur das ich von einem allgemeinen $n_0$ starte. Darf ich es dann trotzdem als "Prinzip der vollständigen Induktion" bezeichnen? Ich denke schon. Falls nicht, einfach weglassen.

Unknown: Ist eingearbeitet

---

Du kannst nicht beweisen, dass vollstaendige Induktion funktioniert. Das Induktionsprinzip ist ein Axiom. Am einsichtigsten lautet es so (eine Version des fuenften Peano-Axioms in heutiger Zaehlweise):

Fuer $M\subset\mathbb{N}=\{1,2,3,\ldots\}$ gelte $1\in M$ und $n\in M\Rightarrow n+1\in M$. Dann ist $M=\mathbb{N}$.

Man sieht $1\in M\Rightarrow1+1=2\in M\Rightarrow2+1=3\in M\Rightarrow\ldots$, also doch wohl $M=\{1,2,3,\ldots\}=\mathbb{N}$. Ein Beweis ist das aber nicht, denn da ich das Induktionsprinzip nicht mit sich selber beweisen kann, bleibt es bei der angedeuteten unvollstaendigen Induktion. Daraus folgt die Notwendigkeit, das Induktionsprinzip explizit als Axiom zu formulieren.

Kurz gesagt waere mein Vorschlag, das Wort Beweis an den kritischen Stellen durch Veranschaulichung oder dergleichen zu ersetzen.

---

Statt "beweisen wir folgende Aussage" könnte man "betrachten wir folgende Aussage" schreiben.

Veranschaulichung passt hier finde ich nicht so gut. Bei Wikipedia wird es mit Hilfe von Dominos veranschaulicht, da ist es was anderes. Allerdings fällt mir auch gerade kein besseres Wort für ein. 

Ein einleitender Satz würde es ja auch tun.

---

Hallo Bruce!

Zum Beweis der Gauß'schen Summenformel steuere ich gerne noch ein Schritt-für-Schritt-Tutorial bei!