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:

  1. Induktionsanfang: Überprüfung der Aussage P für das kleinste Element einer wohlfundierten Ordnung.
  2. 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!