Induktion

Induktion ist eine Methode, um Aussagen zu beweisen, die für alle natürlichen Zahlen gelten.

Die Idee ist zu zeigen, dass wenn eine Aussage für die erste Zahl gilt, und wenn sie für eine beliebige Zahl $ \large k $ gilt, sie dann auch für $ \large k+1 $ gelten muss. Auf diese Weise zeigt man, dass die Aussage für alle $ \large n $ gilt.

Induktion funktioniert wie eine Reihe von Dominosteinen: Wenn der erste Stein fällt (der Basisfall), und jeder Stein den nächsten zum Fallen bringt (der Induktionsschritt), dann fallen alle Steine in der Reihe.

Vorgehensweise

Ein Beweis durch Induktion besteht normalerweise aus drei Schritten:

1. Basis: Zeige, dass die Aussage für die erste natürliche Zahl gilt, typischerweise $ \large n=1 $.
2. Induktionsannahme: Nimm an, dass die Aussage für ein beliebiges $ \large n=k $ gilt.
3. Induktionsschritt: Verwende die Annahme, um zu zeigen, dass die Aussage auch für $ \large n=k+1 $ gilt.

Beispiel 1

Wir wollen durch Induktion beweisen, dass die Summe der ersten $ \large n $ natürlichen Zahlen ist

$$ \large 1 + 2 + \cdots + n = \frac{n(n+1)}{2} $$

Basis:

Für $ \large n=1 $ erhalten wir $ \large 1 = \frac{1 \cdot (1+1)}{2} = 1 $. Die Aussage ist wahr.

Induktionsannahme:

Nehmen wir an, die Aussage gilt für $ \large n=k $:

$$ \large 1 + 2 + \cdots + k = \frac{k(k+1)}{2} $$

Induktionsschritt:

Für $ \large n=k+1 $ erhalten wir:

$$ \large 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) $$

$$ \large = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} $$

Dies ist dieselbe Formel mit $ \large n=k+1 $. Somit ist die Aussage für alle $ \large n $ bewiesen.

Beispiel 2

Wir wollen durch Induktion beweisen, dass $ \large 5^n - 2^n $ für alle $ \large n \in \mathbb{N} $ immer durch 3 teilbar ist.

Basis:

Für $ \large n=1 $ erhalten wir $ \large 5^1 - 2^1 = 3 $, was durch 3 teilbar ist.

Induktionsannahme:

Nehmen wir an, die Aussage gilt für $ \large n=k $:

$$ \large 5^k - 2^k = 3m $$

für eine ganze Zahl $ \large m $.

Induktionsschritt:

Für $ \large n=k+1 $ beginnen wir damit, die Potenzen umzuschreiben:

$$ \large 5^{k+1} - 2^{k+1} = 5 \cdot 5^k - 2 \cdot 2^k $$

Nun wollen wir ein Glied mit $ \large (5^k - 2^k) $ zusammenfassen. Deshalb schreiben wir $ \large -2 \cdot 2^k $ als $ \large -5 \cdot 2^k + 3 \cdot 2^k $ um. Dann erhalten wir:

$$ \large 5 \cdot 5^k - 2 \cdot 2^k = 5 \cdot 5^k - 5 \cdot 2^k + 3 \cdot 2^k $$

Nun können die beiden ersten Glieder zusammengefasst werden:

$$ \large = (5^k - 2^k)\cdot 5 + 3 \cdot 2^k $$

Nach der Induktionsannahme ist $ \large 5^k - 2^k $ durch 3 teilbar, und $ \large 3 \cdot 2^k $ ist offensichtlich ebenfalls durch 3 teilbar. Somit ist der gesamte Ausdruck durch 3 teilbar, und die Aussage ist für $ \large n=k+1 $ bewiesen.

Induktionsbeweise sind ein zentrales Werkzeug in der Mathematik. Sie werden verwendet, um Formeln, Eigenschaften von Folgen, Teilbarkeit und vieles mehr zu beweisen.

Die Methode zeigt, wie eine Aussage für unendlich viele Zahlen gelten kann, indem man jeden Schritt in der Folge logisch mit dem nächsten verbindet.