Vollständige Induktion

Die vollständige Induktion ist ein Beweisverfahren, das häufig verwendet wird, um Aussagen über natürliche Zahlen zu beweisen, wobei Sie auch Aussagen über andere Mengen beweisen kann (z.B.: die Zweierpotenzen). Sie basiert auf der Idee, eine Aussage in drei Schritten zu beweisen: dem Basisfall, der Induktionshypothese und dem Induktionsschritt.

Dies wäre das typische Vorgehen, wenn man eine Aussage über $\mathbb{N}$ beweisen.

  1. Basisfall: Im ersten Schritt zeigt man, dass die Aussage für einen Anfangswert gilt. Meistens wird hierfür der Wert $n = 1$ oder $n = 0$ verwendet. Dieser Schritt legt den Grundstein des Beweises, da er zeigt, dass die Behauptung zumindest für diesen speziellen Fall zutrifft.
  2. Induktionshypothese: Im zweiten Schritt nimmt man an, dass die Aussage für eine beliebige fixe Zahl $k \in \mathbb{N}$ gilt. Sie bildet die Voraussetzung für den nächsten Schritt.
  3. Induktionsschritt: Im dritten Schritt wird gezeigt, dass, wenn die Aussage für $k$ gilt, sie auch für $k + 1$ gilt. Hierbei wird die Induktionsannahme genutzt, um zu beweisen, dass falls es für $k$ gilt, es auch für $k + 1.$

Wenn sowohl der Basisfall als auch der Induktionsschritt bewiesen sind, folgt aus dem Prinzip der vollständigen Induktion, dass die Aussage für alle natürlichen Zahlen $n$ gilt.

Asymptotisches Wachstum

Asymptotisches Wachstum beschreibt, wie sich eine Funktion verhält, wenn ihre Eingabewerte gegen unendlich streben. Der Fokus liegt darauf, wie stark eine Funktion im Vergleich zu anderen wächst.

Dabei gilt:

Seien $f,g: \mathbb{N} \to \mathbb{R}^{+}$ zwei Funktionen. Wir sagen, dass $f$ asymptotisch schneller wächst als $g$, wenn

                                                          $\\lim_{n \\to \\infty} \\frac{g(n)}{f(n)} = 0$.

L'Hôpital's Regel. Angenommen, die Funktionen $f:\mathbb{R}^{+}→\mathbb{R}^{+}$ und $g : \mathbb{R}^{+} \to \mathbb{R}^{+}$ sind differenzierbar, und es gilt:

                                          $\\lim_{x \\to \\infty} f(x) = \\lim_{x \\to \\infty} g(x) = \\infty$

und für alle $x \in \mathbb{R}^{+}$, $g'(x) \neq 0$. Und falls $\lim_{x \to \infty} \frac{f'(x)}{g'(x)} = C \in \mathbb{R}{0}^{+}$ oder$\lim{x \to \infty} \frac{f'(x)}{g'(x)} = \infty$ dann gilt: