Skip to content Skip to navigation

Definition vollständige Induktion

Erklärung vollständige Induktion

Beispiel 1: Der kleine Gauß

Beispiel 2: Bernoulli-Ungleichung

 

 

Definition vollständige Induktion

Merke

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

Merke

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ß

Beispiel

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{align} \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{align} $$

 

Beispiel 2: Bernoulli-Ungleichung

Beispiel

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{align} (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{align} $$

Beliebte Inhalte auf Schulminator