Vollständige Induktion Erklärung und Beispiel
Definition vollständige Induktion
Sei $n_0 \in \mathbb{N}$ fest. Für jedes $n \geq n_0$ sei $A(n)$ eine Aussage. Es gelte:
- $A(n_0)$ ist wahr.
- Für jedes $n \geq n_0$ ist $A(n) \Rightarrow A(n+1)$ wahr.
Dann ist die Aussage $A(n)$ für alle natürlichen Zahlen $n \geq n0$ wahr.
Erklärung vollständige Induktion
Wollen wir von einer Aussage zeigen, dass sie für alle natürlichen Zahlen (oder ab einem bestimmten Wert an) gilt, so teilen wir den Beweis in 3 Teile auf:
- Den Induktionsanfang (IA) beim kleinsten Element $n_0$ rechnen wir für diese feste Zahl einfach nach.
- In der Induktionsvoraussetzung (IV) legen wir die Grundlage für den Induktionsschritt, indem wir von der Richtigkeit der Aussage für ein beliebiges aber festes $n \geq n_0$ ausgehen.
- Im Induktionsschritt (IS) versuchen wir nun die Aussage, basierend auf der Induktions- voraussetzung, auch für $n + 1$ zu zeigen. Ist die zu beweisende Aussage zum Beispiel eine Gleichung (oder Ungleichung), so formen wir den linken Teil der Gleichung für $n + 1$ so um, dass ein Teil genau den linken Teil der Gleichung für $n$ darstellt. Nun setzen wir für diesen mithilfe der Induktionsvoraussetzung den rechten Teil der Gleichung für n ein.
Wenn wir jetzt den gesamten Term wieder in den rechten Teil der Gleichung für $n + 1$ umformen, so sind wir fertig.
Nun ergibt sich die Aussage folgendermaßen für alle Zahlen $n \geq n_0$:
Im Induktionsanfang zeigen wir, dass die Aussage für $n_0$ gilt. In der Induktionsvoraussetzung setzen wir nun in Gedanken $n := n_0$.
Im Induktionsschritt haben wir gezeigt, dass die Aussage also auch für $n+1 = n_0 +1$ gilt.
Nun setzen wir in der IV $n := n_0 +1$ und zeigen im IS, dass die Aussage für $n+1 = (n_0 +1)+1 = n_0 +2$ gilt. Dann $n := n_0 +2$, also gilt die Aussage auch für $n + 1 = (n_0 + 2 ) + 1 = n_0 + 3$ und so weiter .
Beispiel 1: Der kleine Gauß
Behauptung: Der kleine Gauß $$ \forall n \in \mathbb{N}:\sum\limits_{k=1}^{n}{k} = \frac{n(n+1)}{2} $$
Beweis: IA $(n = 1)$ $$ \sum\limits_{k=1}^{1}{k} = 1 = \frac{1 \cdot 2}{2} = \frac{1 \cdot (1 + 1)}{2} $$ IV: Die Behauptung gelte für ein beliebiges aber festes $n \in \mathbb{N}$.
IS $(n \rightarrow n + 1)$:
$$ \begin{aligned} \sum\limits_{k=1}^{n+1}{k} &= \sum\limits_{k=1}^{n}{k + (n + 1)} \\ &\overset{IV}{=} \frac{n(n+1)}{2} + n + 1 \\ &= \frac{n^2 + n}{2} + \frac{2n + 2}{2} \\ &= \frac{n^2 + 3n + 2}{2} \\ &= \frac{(n+1)(n+2)}{2} \\ &= \frac{(n+1)((n+1)+1)}{2} \\ \end{aligned} $$
Beispiel 2: Bernoulli-Ungleichung
Sei $ -1 \lt x \in \mathbb{R}$ beliebig.
IA $(n = 1)$: $$ (1 + x)^1 = 1 + x = 1 + 1 \cdot x $$
also insbesondere: $$ (1 + x)^1 \geq 1 + 1 \cdot x $$
IV: Die Behauptung gelte für ein beliebiges aber festes $n \in \mathbb{N}$.
IS $(n \rightarrow n + 1)$: $$ \begin{aligned} (1+x)^{n+1} &= (1+x)^n \cdot (1+x) \\ &\overset{IV}{\geq} (1 + nx) \cdot (1+x) \\ &= 1+nx+x+\underbrace{nx^2}_{\geq 0} \\ &\geq 1+nx+x \\ &= 1+(n+1)x \\ \end{aligned} $$
