Vollständige Induktion

Aussagen

Note 1

In der Logik versteht man unter Aussagen sprachliche Gebilde, bei denen es sinnvoll ist zu fragen, ob sie wahr oder falsch sind.

Example 1

Beispiele für allgemeine Aussagen:

In jedem Trapez ist die Mittelparallele gleich der halben Summe der beiden Grundseiten.
Alle geraden Zahlen sind durch 2 teilbar.

Dazu passende spezielle Aussagen:

Im Trapez mit den Grundseiten 2 cm und 4 cm beträgt die Mittelparallele 3 cm.
46 ist durch 2 teilbar.

Deduktion und Induktion

Note 2

Der Übergang von allgemeinen Aussagen zu speziellen Aussagen heisst Deduktion. Die Deduktion bereitet keine Schwierigkeiten: Sie ist ein logisches Schlussverfahren, das immer gilt. Aus einer wahren allgemeinen Aussage folgt stets eine wahre spezielle Aussage.

Der Übergang von speziellen Aussagen zu allgemeinen Aussagen heisst Induktion. Induktion ist deutlich anspruchsvoller, da sie sowohl richtige als auch falsche Schlussfolgerungen liefern kann.

Example 2

46 ist durch 2 teilbar.

→ Also sind alle zweistelligen Zahlen durch 2 teilbar. (falsch)
→ Also sind alle geraden Zahlen durch 2 teilbar. (richtig)

In den Naturwissenschaften ist Induktion unentbehrlich. Physiker und Chemiker formulieren aus Experimenten allgemeine Gesetze, Mediziner untersuchen durch Testreihen mögliche Nebenwirkungen von Medikamenten. Absolute Gültigkeit lässt sich dabei jedoch nicht erreichen. In der Mathematik hat diese Form der Induktion deshalb nur heuristischen Wert.

Vollständige Induktion

Exercise 1: Mersenne-Zahlen

Nach Marin Mersenne (1588–1648) sind die Zahlen der Gestalt $2^p-1$ , wobei $p$ eine Primzahl ist, benannt. Berechne die ersten vier Zahlen dieser Art und vermute eine allgemeine Aussage. Kann man sie beweisen oder widerlegen?

Solution

$2^2-1=3$ , $2^3-1=7$ , $2^5-1=31$ , $2^7-1=127$ sind alle prim. Aber $2^{11}-1=2047=23\cdot89$ .

Die Aufgabe verdeutlicht, dass eine Aussage in speziellen Fällen zwar zutreffen kann, sie dadurch jedoch noch nicht allgemein gültig ist. Da es unmöglich ist, alle Einzelfälle zu überprüfen, benötigt man ein Beweisverfahren, mit dem sich die Allgemeingültigkeit einer Aussage feststellen lässt.

Ein solches Verfahren kennt die Mathematik: die vollständige Induktion. Sie wird ausschliesslich in der Mathematik verwendet, um Aussagen über natürliche Zahlen zu beweisen. Im Unterschied zu den unvollkommenen Induktionsverfahren der Naturwissenschaften ist sie vollständig: Ein einmal geführter Beweis lässt keinen Zweifel an der Gültigkeit der Aussage.

Das Verfahren der vollständigen Induktion wurde von Blaise Pascal (1623–1662) im Zusammenhang mit dem nach ihm benannten Zahlendreieck entwickelt. Die Bezeichnung selbst geht auf Augustus de Morgan (1806–1871) zurück.

Note 3

1889 hat der italienische Mathematiker Giuseppe Peano die Menge der natürlichen Zahlen durch fünf Axiome charakterisiert. Als fünftes Axiom, das sogenannte Induktionsaxiom, formulierte er sinngemäss:

Eine Eigenschaft, die der $1$ zukommt und mit jeder natürlichen Zahl auch ihrem Nachfolger, kommt allen natürlichen Zahlen zu.

Note 4: Das Verfahren der vollständigen Induktion

Zusammen mit diesem sogenannten Induktionsaxiom genügen also praktisch zwei Schritte, um zu zeigen, dass eine Aussage für alle natürlichen Zahlen $n\in\mathbb{N}$ richtig ist. Mit Peano sind es drei Schritte:

Induktionsverankerung: Man beweist die Vermutung für kleine $n\in\mathbb{N}$ , in der Regel für $n=1$ .
Induktionsschritt: Man beweist, dass die Behauptung für $n+1$ richtig ist, unter der Annahme (Hypothese), dass sie für $n$ richtig ist.
Induktionsschluss: Weil die Behauptung gemäss 1. für $n=1$ richtig ist, ist sie gemäss 2. auch für $n=2$ richtig, also gemäss 2. auch für $n=3$ richtig, also gemäss 2. auch für $n=4$ richtig, $\dots$

Exercise 2: Summenformel

Finde eine Formel für die $n$ -te Partialsumme der Folge

1\quad2\quad3\quad4\quad5\quad\dots\quad n

Beweise anschliessend deine Vermutung mit vollständiger Induktion.

Solution

Man vermutet $s_n=(1+n)\cdot\frac{n}{2}$ .

Für $n=1$ gilt $s_1=(1+1)\cdot\frac{1}{2}=1$ , also ist die Aussage verankert.

Induktionsschritt:

s_{n+1}=s_n+(n+1)=(1+n)\cdot\frac{n}{2}+(n+1)=\frac{n^2+n}{2}+(n+1)=\frac{(n+1)(n+2)}{2}.

Damit ist die Aussage auch für $n+1$ richtig, falls sie für $n$ gilt.

Exercise 3: Summenformel II

Finde zuerst die Darstellung für $a_n$ , dann eine Formel für die Summe, und beweise deine Vermutung anschliessend mit vollständiger Induktion.

\frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}+\ldots+a_n

5+17+29+41+\ldots+a_n

1+8+27+\ldots+a_n

Solution

a) $a_n=\frac{1}{n(n+1)}$ . Man vermutet $s_n=\frac{n}{n+1}$ .
b) $a_n=12n-7$ . Man vermutet $s_n=6n^2-n$ .
c) $a_n=n^3$ . Man findet $s_n=\Big(\tfrac{n(n+1)}{2}\Big)^2$ .

Exercise 4: Durch 3 teilbar

Zeige, dass $n^3+5n$ für alle $n\in\mathbb{N}$ durch $3$ teilbar ist.

Solution

Für $n=1$ : $1^3+5\cdot1=6$ ist durch 3 teilbar.

Induktionsschritt: Sei $n^3+5n$ durch 3 teilbar. Dann gilt

(n+1)^3+5(n+1)=n^3+5n+3(n^2+n+2),

was wieder durch 3 teilbar ist. Damit folgt die Behauptung.

Historisches zur vollständigen Induktion

Der erste, der dieses Schlussverfahren angewendet hat, war `Blaise Pascal (1623–1662). 1654 bewies er damit eine Eigenschaft des sogenannten Pascal’schen Dreiecks.

Dieses Zahlendreieck entsteht aus den Koeffizienten der Binome $(a+b)^n$ :

\begin{align} (a+b)^0 &= 1\notag\\ (a+b)^1 &= a+b\notag\\ (a+b)^2 &= a^2+2ab+b^2\notag\\ (a+b)^3 &= a^3+3a^2b+3ab^2+b^3\notag\\ (a+b)^4 &= a^4+4a^3b+6a^2b^2+4ab^3+b^4\notag\\ \dots &\dots\notag \end{align}

1\\ 1\quad\quad1\\ 1\quad\quad2\quad\quad1\\ 1\quad\quad3\quad\quad3\quad\quad1\\ 1\quad\quad4\quad\quad6\quad\quad4\quad\quad1\\ \dots

Eigenschaften:

Jede innere Zahl ist die Summe der beiden darüber stehenden Zahlen.
Von zwei benachbarten Zahlen einer Zeile verhält sich die untere zur oberen wie die Anzahl Zahlen links der oberen zur Anzahl Zahlen rechts der unteren.

Erkenntnistheoretischer Ausblick

Definition 1: Induktion

Induktion bezeichnet das Schlussverfahren, bei dem aus Einzelfällen auf den allgemeinen Fall geschlossen wird.

Definition 2: Deduktion

Deduktion bezeichnet das Schlussverfahren, bei dem aus dem allgemeinen Fall auf den Einzelfall geschlossen wird.

Deduktive Schlüsse sind zwingend gültig, sofern die Prämissen stimmen. Induktive Schlüsse dagegen können zutreffen, müssen es aber nicht.

Example 3

Leonhard Euler (1707–1783) fand: Für $n=1,2,\dots,40$ liefert

p=n^2-n+41

stets eine Primzahl. Induktiv könnte man schliessen, dies gelte allgemein. Für $n=41$ ergibt sich jedoch $p=41^2$ , keine Primzahl.

Die Naturwissenschaften sind gleichwohl auf Induktion angewiesen: Aus endlich vielen Beobachtungen werden allgemeine Gesetze abgeleitet. Ihre Gültigkeit ist deshalb nicht absolut, sondern nur mit sehr hoher Wahrscheinlichkeit gegeben.

Note 5

Nur die in der Mathematik verwendete Methode der vollständigen Induktion ist ein unanfechtbares Beweisverfahren.