Vollständige Induktion Erklärung und Beispiel

26 November 2020
☆ 70% (Anzahl 4), Kommentare: 0
Erklärung

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:

  1. Den Induktionsanfang (IA) beim kleinsten Element $n_0$ rechnen wir für diese feste Zahl einfach nach.
  2. 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.
  3. 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} $$

Wie hat dir dieses Lernmaterial gefallen?
Durchschnittliche Bewertung: 3.5 (Anzahl 4)

Kommentare