Vollständige Induktion

[Christian Kruse]

你好 Cheatah,

Ich bin der Überzeugung, daß wenn man den Induktionsschritt kennt, dann
findet man eine ebensogute nicht-rekursive Lösung.

Ich finde, vollständige Induktion ist eine der leichtesten
Beweismethoden.

Ja… ich muss mich gerade mit anderen Beweismethoden herumschlagen, für
Analysis1, das ist manchmal wirklich zum Haare raufen. Dagegen fand ich die
Induktionsbeweise recht einfach. Beispiel von heute (wo ich wirklich dran
herumgerätselt habe):

Beweise: Ist latex_{n\in\mathbb{N}} \subset \mathbb{R}[/latex] eine Folge mit [latex]a_n > 0 \forall n \in \mathbb{N}[/latex], so ist latex_{n\in\mathbb{N}}[/latex] genau dann eine Nullfolge, wenn [latex]\lim_{n\rightarrow\infty}\frac{1}{a_n} = +\infty[/latex] gilt.

Beweis:

[elatex]
\begin{tabular}{l|r}
$\forall \epsilon > 0 \exists n_{\epsilon}\in\mathbb{N}: |a_n| < \epsilon\forall n \ge n_{\epsilon}$&$\forall k > 0 \exists n_k \in \mathbb{N}: \frac{1}{a_n} > k \forall n \ge n_k$
\end{tabular}
[/elatex]

Sei [latex]k > 0[/latex]. Setze [latex]\epsilon := \frac{1}{k} > 0[/latex]. Wegen [latex]a_n \rightarrow_{n \rightarrow \infty} 0[/latex] finden wir immer ein [latex]n_{\epsilon} \in \mathbb{N}[/latex] mit [latex]|a_n| = a_n < \epsilon \forall n \ge n_{\epsilon}[/latex]. Daraus folgt: [latex]a_n < \frac{1}{k} \Leftrightarrow \frac{1}{a_n} > k \forall n \ge n_k[/latex].

Wir haben erreicht, dass wir ein [latex]n_{\epsilon(k)}\in\mathbb{N}[/latex] mit [latex]\frac{1}{a_n} > k \forall n \ge n_{\epsilon}[/latex] von [latex]k > 0[/latex] ausgehend finden.

Setze [latex]n_k := n_{\epsilon} \Rightarrow[/latex]: das gleiche gilt für die rechte Seite.

Für die andere Richtung läuft der Beweis analog ab. Das erspare ich mir jetzt aber hierhin zu schreiben ;) QED.

An dem Beweis habe ich fast eine Stunde gesessen… dafür sollte er (bis auf Fipptehler) richtig sein, die Musterlösung sieht ähnlich aus ;)

再见,
 克里斯蒂安