vollständige Induktion

up:: Mat1 MOC

Beispiel

1. Induktionsvoraussetzung (IV)

$\sum _{i=0}^{n}i=\frac{1}{2}n\cdot (n+1)$

2. Induktionsanfang n = 0 (IA)

Setze $n=0$ und überpüfe:

$$\begin{array}{rl}\sum _{i=0}^{0}0& =\frac{1}{2}0\cdot (0+1)\\ 0& =0\end{array}$$

3. Induktionschrintt n = n+1 (IS)

Setzte $n=n+1$ und vereinfache:

$$\begin{array}{rl}\sum _{i=0}^{n+1}i& =\frac{1}{2}(n+1)\cdot (n+1+1)\\ & =\frac{1}{2}(n+1)\cdot (n+2)\end{array}$$

4. Induktionsvoraussetzung benutzen um Induktionschrintt durch zu führen.

$$\begin{array}{rl}\sum _{i=0}^{n+1}i& =\left(\sum _{i=0}^{n}i\right)+(n+1)\\ & =\frac{1}{2}n\cdot (n+1)+(n+1)\\ & =\frac{1}{2}n\cdot (n+1)+\frac{2\cdot (n+1)}{2}\\ & =\frac{1}{2}(n\cdot (n+1)+2\cdot (n+1))\\ & =\frac{1}{2}(n+1)\cdot (n+2)\end{array}$$

Definition

Hat man eine Aussage der Form:
Für alle $n\in \mathbb{N}$ mit $n\ge n_0$ gilt $A(n)$,
dann kann mann diese Methode der vollständige Induktion beweisen (falls sie wahr ist):

1. Zeige das $A(n_0)$ gilt, dass also die Aussage für die erste Zahl $n_0$ wahr ist. Dies nennt man den Induktionsanfang. (IA)
2. Zeige, dass $A(n)⟹A(n+1)$ für $n\ge n_0$ gilt, das also, falls die Aussage für ein $n\ge n_0$ gilt, sie auch für $n+1$ gilt. Dies nennt man den Induktionschrintt.
   Die Aussage $A(n)$ heißt in diesem Zusammenhang auch Induktionsvoraussetzung.

Typische Arten von vollständige Induktions Aufgaben:

• Summen ( kleiner Gauß )
• Ungleichheiten ( $2^n\ge n^2$ )
• Teilbarkeitsaufgaben

starke Induktion

Bei der vollständige Induktion kann man
manchmal nicht aus $A(n)$ diereckt $A(n+1)$ folgern.
Mann benötigt dann:

$A(k)$ ist wahr für alle $n_0\le k\le n$

Mann nennt dies starke Induktion.

1. Zeige, dass $A(n_0)$ wahr ist.

2. Folgere aus: A(k) ist wahr für alle $n_0\le k\le n$, dass $A(n+1)$ wahr ist.

siehe: Teilbarkeitsaufgaben

Link to original

Beispiele:
kleiner Gauß
Türme von Hanoi

siehe auch:
Primzahl