Die Induktion schließt vom Einzelfall auf die allgemeine Regel. Es ist der Beweis zu erbringen, dass die Regel für jeden Einzelfall gilt.
Vollständige Induktion
Die Vollständige Induktion wird oft als Beweismittel für die Richtigkeit von bestimmten, aus Reihen abgeleiteten Formeln, wie zum Beispiel der Summenformeln von arithmetischen oder geometrischen Reihen, angewendet. Um die Summe einer vorgegebenen Reihe richtig zu „entdecken“, ist viel Intuition und Fleiß erforderlich. Umso wichtiger ist dann der Beweis, dass die Summenformel nicht nur für die Anzahl der getesteten Glieder der vorgegebene Reihe richtig ermittelt wird, sondern für beliebig viele Glieder dieser Reihe.
Gegeben sei eine Aussage P⊆N (P ist i.A. eine Formel, die als Ergebnis wieder eine natürliche Zahl liefert). Das angewandte Schlussverfahren geht davon aus, dass eine Aussage P(imin) über die natürlichen Zahlen (i∈ℕ) richtig ist (Induktionsanfang). Kann nun gezeigt werden, dass die Aussage auch für die nächst größere ganze Zahl, nämlich i+1, auch richtig ist, dann gilt die Aussage P(n) auch für jedes n∈ℕ, da ja dieser Schritt beliebig oft mit dem gleichen Ergebnis vollzogen werden kann.
Induktive Schlüsse werden also in zwei Schritten ausgeführt:
- Induktionsanfang: Überprüfung der Aussage P für das kleinste Element einer wohlfundierten Ordnung.
- Induktionsschritt: Schluss von i auf i+1 (→ Beweis).
Prädikatenlogisch wird das so formuliert:
\( \left\{ {P\left( { {i_{ \min } } } \right) \wedge \left[ {\forall i \in N:\left( {P\left( i \right) \Rightarrow P\left( {i + 1} \right)} \right)} \right]} \right\} \Rightarrow \forall n \in N:P\left( n \right) \) Gl. 26
Beispiel 1: Summenbildung arithmetischer Reihen
Eine Reihe stellt die Summe der Glieder einer Folge dar
\({s_n} = {a_0} + {a_1} + {a_2} + {a_3} + \,.....\, + {a_n}\) wobei n∈∞
typisch für eine arithmetische Reihe ist, dass benachbarte Glieder sich stets durch den gleichen konstanten Betrag d unterscheiden. Dabei kann ein Anfangsglied \( a_0 \) beliebiger Größe auftreten.
\({s_n} = {a_0} + \left( { {a_0} + d} \right) + \left( { {a_0} + 2d} \right) + \left( { {a_0} + 3d} \right) + \,.....\, + \left( { {a_0} + nd} \right)\) wobei \( n∈∞; \; a_0, d∈ℤ \)
Das allgemeine Glied der Reihe lautet dann
\({a_n} = {a_0} + n \cdot d\) wobei n∈∞
z.B. Arithmetische Reihe bestehend aus 6 Gliedern mit n=5; a0=5; d=3
n = (0) 1 2 3 4 5
s5 = 5 + 8 + 11 + 14 + 17 + 20 = 75
1. Herleitung der Summenformel
Anwendung der Gausschen Methode zur Bildung der Summenformel
n = (0) 1 2 3 4 5
s5 = 5 + 5 + 5 + 5 + 5 + 5 = 6·5 | (n+1)·a0
+ 3·(0 + 1 + 2 + 3 + 4 + 5) = 3·3·5 | d·(n+1)·n/2 (Mittelwert)
6·5 + 3·3·5 = 75
\( {s_n} = \left( {n + 1} \right) · \left( { {a_0} + \frac{n}{2} · d} \right) \) wobei n∈∞
2. Beweis
Beim Beweis wird davon ausgegangen, dass die Summenformel für jedes n∈∞ gelten muss.
Induktionsanfang:
\( {s_1} = {a_0} + \left( { {a_0} + d} \right) = 2{a_0} + d \) bzw. laut Summenformel \( {s_1} = 2 \cdot \left( { {a_0} + \frac{1}{2} \cdot d} \right) = 2{a_0} + d \)
Induktion:
Grundsätzlich gilt \( P(n+1) = P(n) + a_{n+1} \), also:
\( {s_{n + 1} } = {s_n} + {a_{n + 1} } \) wobei n∈∞
Einsetzen der Summenformel und des allgemeinen Gliedes für n und n+1 zeigt,
\( \left( {n + 2} \right) \cdot \left( { {a_0} + \frac{ {n + 1} }{2} \cdot d} \right) = \left( {n + 1} \right) \cdot \left( { {a_0} + \frac{n}{2} \cdot d} \right) + {a_0} + \left( {n + 1} \right) \cdot d \)
\( \left( {n + 2} \right) \cdot \left( {2{a_0} + \left( {n + 1} \right) \cdot d} \right) = \left( {n + 1} \right) \cdot \left( {2{a_0} + n \cdot d} \right) + 2{a_0} + 2\left( {n + 1} \right) \cdot d \)
\(n \cdot \left( {2{a_0} + nd + d} \right) + 2 \cdot \left( {2{a_0} + nd + d} \right) = n \cdot \left( {2{a_0} + n \cdot d} \right) + \left( {2{a_0} + n \cdot d} \right) + 2{a_0} + 2nd + 2d\)
\(2n{a_0} + {n^2}d + nd + 4{a_0} + 2nd + 2d = 2n{a_0} + {n^2}d + 2{a_0} + nd + 2{a_0} + 2nd + 2d\)
\(2n{a_0} + {n^2}d + 3nd + 4{a_0} + 2d = 2n{a_0} + {n^2}d + 3nd + 4{a_0} + 2d\)
dass die linke Seite gleich der rechten Seite ist.
q.e.d.
Beispiel 2:
Es die Summenformel für die geometrische Reihe
\( {s_n} = 1 + q + {q^2} + {q^3} + ... + {q^n} = \frac{ {1 - {q^{n + 1} } } }{ {1 - q} } \)
abzuleiten und deren Richtigkeit durch vollständige Induktion zu beweisen.
1. Herleitung
\( I. \; {s_n} = 1 + q + {q^2} + {q^3} + ... + {q^n} \) | Erweitern mit q
\( II. \; q \cdot {s_n} = q + {q^2} + {q^3} + ... + {q^n} + {q^{n + 1} } \) | Subtraktion I – II
\( (1 - q) · {s_n} = 1 - {q^{n + 1} } \) | Umstellen nach sn
\( {s_n} = \frac{ {1 - {q^{n + 1} } } }{ {1 - q} } \) und \( {a_n} = {q^n} \)
2. Beweis
Induktionsanfang
\( {s_1} = 1 + q\) bzw. \({s_1} = \frac{ {1 - {q^2} } }{ {1 - q} } = \frac{ {\left( {1 - q} \right) · \left( {1 + q} \right)} }{ {\left( {1 - q} \right)} } = 1 + q \) ⇒ P(s1) = wahr
Induktion
n → n +1
\( {s_{n + 1} } = {s_n} + {a_{n + 1} } \) wobei n∈∞ | Behauptung
\( \frac{ {1 - {q^{\left( {n + 1} \right) + 1} } } }{ {1 - q} } = {s_n} + {q^{\left( {n + 1} \right)} } \)
\( 1 - {q^{n + 2} } = (\frac{ {1 - {q^{n + 1} } } }{ {1 - q} } + {q^{n + 1} }) \cdot (1 - q) \) | Erweitern mit (1-q)
\( 1 - {q^{n + 2} } = (1 - {q^{n + 1} } + {q^{n + 1} } \cdot (1 - q)) \) | Ausmultiplizieren
\( 1 - {q^{n + 2} } = (1 - {q^{n + 2} }) \)
q.e.d.
Beispiel 3:
Es sei die Behauptung \({2^x} \ge {x^2};\,\,x \ge 4\) zu beweisen.
Beweis:
Induktionsanfang
Mit xmin=4 ergibt sich, dass, da \({2^4} \ge {4^2} \Rightarrow 16 \ge 16\), die Behauptung erfüllt ist.
Induktion
x → x + 1
\({2^{x + 1} } \ge {\left( {x + 1} \right)^2} \Rightarrow \,2 \cdot {2^x} \ge {x^2} + 2x + 1\)
da laut Behauptung \( 2^x \ge x^2 \), ist auch \(2 \cdot {2^x} \ge 2 \cdot {x^2}\), also \({2^{x + 1} } = 2 \cdot {2^x} \ge 2 \cdot {x^2} = 2x \cdot x\)
andererseits ist \( 2^{x + 1} = 2 · {2^x} \ge {x^2} + 2x + 1 = x·\left( x + 2 + \frac{1}{x} \right) \)
Hier stehen sich zwei Aussagen gegenüber. Wegen \(x \ge 4\) gilt:
\( 2^{x + 1} \ge 2x · x \ge x·\left( x + 2 + \frac{1}{x} \right) \)
der Term \( \frac{1}{x} \) kann gegenüber x+2 vernachlässigt werden
\( 2x \ge x + 2 \)
Fazit: die Aussage ist ab x = 4 stets richtig!
Noethersche Induktion
Das Beweisprinzip der Induktion ist nicht auf die Struktur der natürlichen Zahlen beschränkt. Die einzige Voraussetzung ist, dass die zugrundeliegende Struktur einen oder mehrere Anfänge besitzt. Solche Strukturen sind die vollständigen oder wohlbegründeten Ordnungen. Soll gezeigt werden, dass eine Aussage P(x) für alle x gilt, müsste es, um das Gegenteil zu beweisen, wenigstens für ein x geben, für das P(x) falsch ist. Dies führt auf einen Beweis durch Widerspruch. Diese Beweisführung ist nach der deutschen Mathematikerin Emmy NOETHER (1882 - 1935) benannt.
Das Prinzip der Noetherschen Induktion besagt, dass eine Aussage P für alle Elemente einer wohlbegründeten Ordnung ( X,≺) gilt, wenn für jedes Element von X gezeigt werden kann, dass die Aussage für das Element selbst gilt, wenn sie für alle Vorgänger des Elements gilt.
x, y, z seien Elemente einer wohlfundierten Ordnung (X,≺). Wenn für jedesx∈X, für das für jedes y∈X mit y≺x die Aussage P(y) gilt, auch P(x) gilt, dann gilt für jedes z∈X die Aussage P(z).
\( \left\{ {\forall x \in X:\left[ { \forall y \prec x:P(y) \Rightarrow P\left( x \right)} \right]} \right\} \Rightarrow \forall z \in X:P\left( z \right) \) Gl. 27
In der Noetherschen Induktion ist die Bedingung \( \forall y \prec x:P\left(y \right) \) die Induktionsvoraussetzung für P(x). Sie ist also in der Induktion implizit enthalten. Für den Fall, dass x das minimale (kleinste) Element der Ordnung ist, hat x keinen Vorgänger. Folglich ist die Aussage \(\forall y \prec x:P\left( y \right)\) trivial, denn die Aussage P(y) ist dann eine Aussage über die leere Menge! Die Richtigkeit der Aussage P(xmin) ist daher ohne weitere Vorraussetzung zu beweisen, was ja Bedingung für den Induktionsanfang ist.