Drei asymptotische Formeln – Analysis I (Kap. 1-9)

9.6 Drei asymptotische Formeln

9.6.1 Das Wallissche Produkt

Die Formel

\begin{align} π = \lim_{n \to \infty} \frac{1}{n} \frac{{(2^{n} n!)}^{4}}{{((2 n)!)}^{2}} & (9.17) \end{align}

nach John Wallis (1616-1703) wird das Wallissche Produkt genannt.

Um Gleichung (9.17) zu beweisen, wollen wir zuerst für jedes $k \in ℕ_{0}$ das Integral

\begin{array}{l} I_{k} = \int_{0}^{π} \sin^{k} (x) d x \end{array}

mit vollständiger Induktion berechnen.

Für $k = 0$ gilt $I_{0} = π$ und für $k = 1$ gilt $I_{1} = \int_{0}^{π} \sin (x) d x = 2$ . Mit partieller Integration erhalten wir für alle $k \geq 2$

\begin{array}{l} I_{k} & = \int_{0}^{π} \sin^{k} (x) d x = \int_{0}^{π} \sin^{k - 1} (x) \sin (x) d x \\ = {[\sin^{k - 1} (x) (- \cos (x))]}_{0}^{π} + \int_{0}^{π} (k - 1) \sin^{k - 2} (x) \cos^{2} (x) d x \\ = (k - 1) \int_{0}^{π} \sin^{k - 2} (x) (1 - \sin^{2} (x)) d x \\ = (k - 1) (I_{k - 2} - I_{k}), \end{array}

woraus sich die Rekursionsformel

I_{k} = \frac{k - 1}{k} I_{k - 2}

(9.18)

für jedes ganze $k \geq 2$ ergibt.

Somit ist für $n \in ℕ$

\begin{array}{l} I_{2 n} = \frac{2 n - 1}{2 n} I_{2 n - 2} & = \frac{2 n - 1}{2 n} \cdot \frac{2 n - 3}{2 n - 2} \dots \frac{1}{2} I_{0} \\ = \frac{(2 n) (2 n - 1) (2 n - 2) \dots 1}{((2 n) (2 n - 2) \dots 2)^{2}} I_{0} = \frac{(2 n)!}{{(2^{n} n!)}^{2}} \cdot π, \end{array}

wobei wir den Bruch mit $2 n (2 n - 2) \dots 2$ erweitert haben um im Zähler $(2 n)!$ zu erhalten. Auf dieselbe Weise ergibt sich

\begin{array}{l} I_{2 n + 1} = \frac{2 n}{2 n + 1} \cdot \frac{2 n - 2}{2 n - 1} \dots \frac{2}{3} I_{1} = \frac{((2 n) (2 n - 2) \dots 2)^{2}}{(2 n + 1) (2 n) \dots 1} \cdot 2 = \frac{{(2^{n} n!)}^{2}}{(2 n + 1)!} \cdot 2 . \end{array}

Die Folge ${(I_{n})}_{n}$ erfüllt noch eine weitere Eigenschaft: Denn für $x \in [0, π]$ ist $\sin (x) \in [0, 1]$ und somit

\begin{array}{l} \sin^{2 n + 2} (x) \leq \sin^{2 n + 1} (x) \leq \sin^{2 n} (x) \end{array}

für alle $x \in [0, π]$ and $n \in ℕ$ . Durch Integration folgt die Monotonieungleichung

\begin{array}{l} I_{2 n + 2} = \int_{0}^{π} \sin^{2 n + 2} (x) d x \leq I_{2 n + 1} = \int_{0}^{π} \sin^{2 n + 1} (x) d x \leq I_{2 n} = \int_{0}^{π} \sin^{2 n} (x) d x \end{array}

und mittels (9.18) auch

\begin{array}{l} I_{2 n + 2} = \frac{2 n + 1}{2 n + 2} \underset{I_{2 n}}{\underset{︸}{\frac{(2 n)!}{{(2^{n} n!)}^{2}} π}} \leq \frac{{(2^{n} n!)}^{2}}{(2 n + 1)!} 2 \leq I_{2 n} = \frac{(2 n)!}{{(2^{n} n!)}^{2}} π . \end{array}

Wir multiplizieren diese Ungleichungskette mit $\frac{{(2^{n} n!)}^{2}}{(2 n)!} \frac{2 n + 1}{2 n}$ und erhalten

\begin{array}{l} \frac{{(2 n + 1)}^{2}}{2 n (2 n + 2)} π \leq \frac{1}{n} \frac{{(2^{n} n!)}^{4}}{{((2 n)!)}^{2}} \leq \frac{2 n + 1}{2 n} π . \end{array}

Dies beweist die Formel (9.17) nach Wallis unter Anwendung des Sandwich-Lemmas (Lemma 6.2).

9.6.2 Stirling-Formel

Wir verwenden nun das Wallissche Produkt und Taylor-Approximationen, um das asymptotische Verhalten von $n!$ zu bestimmen. Genauer formuliert wollen wir die Stirling-Formel

\begin{align} \lim_{n \to \infty} \frac{n!}{\sqrt{2 π n} {(\frac{n}{e})}^{n}} = 1 & (9.19) \end{align}

beweisen. Diese ist nach James Stirling (1692-1770) benannt und wird auch als $n! \approx \sqrt{2 π n} {(\frac{n}{e})}^{n}$ geschrieben.

Der Grundgedanke für den Beweis von (9.19) ist die Gleichung

\begin{array}{l} \log (n!) = \log (1) + \log (2) + \dots + \log (n) \end{array}

für $n \in ℕ$ genauer zu betrachten, wobei wir die Summe aber durch das Integral $\int_{\frac{1}{2}}^{n + \frac{1}{2}} \log (x) d x$ ersetzen wollen, da dieses einfacher zu berechnen ist.

Für $k \in ℕ$ und $t \in [k - \frac{1}{2}, k + \frac{1}{2}]$ gilt nach Beispiel 9.59

\begin{array}{l} \log (t) = \log (k) + \frac{1}{k} (t - k) + O (\frac{1}{k^{2}}) . \end{array}

Wir erhalten

\begin{array}{l} \int_{k - \frac{1}{2}}^{k + \frac{1}{2}} \log (t) d t = \log (k) + O (\frac{1}{k^{2}}) \end{array}

für alle $k \in ℕ$ , da sich der lineare Term bei der Integration weglöscht.

Für ein festes $n \in ℕ$ und die Summe über $k \in {1, \dots, n}$ folgt daraus

\begin{array}{l} \log (n!) & = \sum_{k = 1}^{n} \log (k) = \sum_{k = 1}^{n} \int_{k - \frac{1}{2}}^{k + \frac{1}{2}} \log (t) d t + \sum_{k = 1}^{n} O (\frac{1}{k^{2}}) = \int_{\frac{1}{2}}^{n + \frac{1}{2}} \log (t) d t + \sum_{k = 1}^{n} O (\frac{1}{k^{2}}) \\ = (n + \frac{1}{2}) \log (n + \frac{1}{2}) - (n + \frac{1}{2}) - c + \sum_{k = 1}^{n} O (\frac{1}{k^{2}}), \end{array}

wobei sich die Konstante $c \in ℝ$ durch Auswerten der Stammfunktion bei der unteren Grenze $\frac{1}{2}$ ergibt. Wiederum nach Taylorapproximation gilt $\log (n + \frac{1}{2}) = \log (n) + \frac{1}{n} \cdot \frac{1}{2} + O (\frac{1}{n^{2}})$ . Wir multiplizieren diese Approximation mit $(n + \frac{1}{2})$ und erhalten (mit $(n + \frac{1}{2}) O (\frac{1}{n^{2}}) = O (\frac{1}{n})$ ) somit

\begin{array}{l} \log (n!) & = (n + \frac{1}{2}) (\log (n) + \frac{1}{2 n} + O (\frac{1}{n^{2}})) - (n + \frac{1}{2}) - c + \sum_{k = 1}^{n} O (\frac{1}{k^{2}}) \\ = (n + \frac{1}{2}) \log (n) + \frac{1}{2} + O (\frac{1}{n}) - n - \frac{1}{2} - c + \sum_{k = 1}^{n} O (\frac{1}{k^{2}}) \\ = \frac{1}{2} \log (n) + n \log (n) - n + a_{n} \end{array}

für eine konvergente Folge ${(a_{n})}_{n}$ in $ℝ$ (wobei wir Proposition 7.28 verwendet haben um die absolut konvergenten Fehlerterme $𝜀_{n} = O (\frac{1}{n^{2}})$ aufzusummieren). Wenden wir die Exponentialabbildung an, so erhalten wir für alle $n \in ℕ$

\begin{align} n! = \sqrt{n} n^{n} e^{- n} b_{n}, & (9.20) \end{align}

wobei $b_{n} = \exp (a_{n})$ ist. Da ${(a_{n})}_{n}$ konvergent ist, ist auch ${(b_{n})}_{n}$ konvergent und der Grenzwert $B = \lim_{n \to \infty} \exp (a_{n}) = \exp (\lim_{n \to \infty} a_{n})$ ist positiv.

Um $B$ zu berechnen, verwenden wir (9.20) gemeinsam mit dem Wallisschen Produkt (9.17). Es gilt

\begin{array}{l} π = \lim_{n \to \infty} \frac{1}{n} \frac{{(2^{n} n!)}^{4}}{{((2 n)!)}^{2}} = \lim_{n \to \infty} \frac{1}{n} \frac{{(2^{n} \sqrt{n} n^{n} e^{- n} b_{n})}^{4}}{{(\sqrt{2 n} {(2 n)}^{2 n} e^{- 2 n} b_{2 n})}^{2}} = \lim_{n \to \infty} \frac{b_{n}^{4}}{2 b_{2 n}^{2}}, \end{array}

da die Potenzen von $2$ , von $n$ und von $e$ sich jeweils direkt kürzen, und die Wurzelterme gemeinsam mit dem $\frac{1}{n}$ vor dem Bruch sich zu einem $\frac{1}{2}$ vereinfachen. Daraus folgt

π = \frac{B^{4}}{2 B^{2}} = \frac{1}{2} B^{2}

und somit muss $B = \sqrt{2 π}$ gelten. Aus Gleichung (9.20) erhalten wir

\lim_{n \to \infty} \frac{n!}{\sqrt{n} {(\frac{n}{e})}^{n}} = \lim_{n \to \infty} b_{n} = \sqrt{2 π},

was zur Stirling-Formel (9.19) äquivalent ist.

Auf Grund der Bedeutung von der Fakultätsfunktion, zum Beispiel in kombinatorischen Überlegungen, ist es nicht verwunderlich, dass die Sterling-Formel vielfache Anwendungen besitzt. In den folgenden Übungen wollen wir einige wenige solcher Anwendungen präsentieren.

Übung 9.60 (Besuche bei der Irrfahrt auf $ℤ$ ).

Wir betrachten eine (diskrete) zufällige Bewegung auf den ganzen Zahlen ausgehend von Null. Also beginnen wir zur Zeit $t = 0$ im Ursprung, hüpfen dann mit Wahrscheinlichkeit $\frac{1}{2}$ entweder nach links auf die Position $- 1$ oder nach rechts auf die Position $1$ . Bezeichnet im Allgemeinen $x_{t} \in ℤ$ die Position zur Zeit $t \in ℕ$ , so bewegen wir uns auf die Zeit $t + 1$ hin wieder entweder links oder rechts mit gleicher Wahrscheinlichkeit von $\frac{1}{2}$ .

Berechnen Sie die Wahrscheinlichkeit, dass man sich zur Zeit $t \in ℕ$ bei Null befindet und approximieren Sie diese mit der Stirling-Formel.

Übung 9.61.

Eine Münze wird $n$ -mal geworfen. Sei $𝜀 > 0$ . Zeigen Sie, dass die Wahrscheinlichkeit, dass die Münze höchstens $(\frac{1}{2} - 𝜀) n$ -mal auf Kopf fällt, für $n \to \infty$ gegen Null geht.

Hinweis: Sie dürfen dabei annehmen, dass $2^{- n} (\binom{n}{k})$ die Wahrscheinlichkeit ist, dass bei $n$ -maligem Wurf die Münze $k$ -mal auf Kopf fällt. Zeigen Sie auch, dass die Funktion $x \in (0, 1) \mapsto x \log (x) + (1 - x) \log (1 - x)$ ein striktes lokales Maximum bei $x = \frac{1}{2}$ hat.

Übung 9.62 (Ein Ausblick auf Algorithmik).

In dieser Übung wollen wir die worst case Geschwindigkeit eines Sortieralgorithmus abschätzen. Sei also gegeben ein Algorithmus, der zu einem Datensatz $a_{1}, \dots, a_{n} \in ℤ$ diesen umordnet, das heisst, eine Abbildung $j : {1, \dots, n} \to {1, \dots, n}$ findet, so dass $a_{j (1)} \leq \dots \leq a_{j (n)}$ . Wir interessieren uns nun für die Zahl $W (n)$ der Anzahl Vergleiche zweier Zahlen des Datensatzes, die der Algorithmus schlimmstenfalls durchführen muss, um den Datensatz zu sortieren. Zeigen Sie, dass eine von $n$ unabhängige Konstante $C > 0$ existiert, so dass $W (n) \geq C n \log (n)$ .

Hinweis.

Zählen Sie die Anzahl Datensätze, die mit $A$ Umsortierungen aus einem fixen Datensatz konstruiert werden können.

9.6.3 Asymptotik der harmonischen Reihe

Für den Beweis der Stirling-Formel wurde eine Kombination von Taylor-Approximation und Integration verwendet, um das asymptotische Verhalten der Reihe $\log (n!) = \sum_{k = 1}^{n} \log (k)$ zu bestimmen. Diese Methode kann auch allgemeiner zur Untersuchung des Divergenzverhaltens von Reihen eingesetzt werden. Zum Beispiel gilt die „asymptotische Entwicklung“

\begin{align} \sum_{k = 1}^{n} \frac{1}{k} = \log (n) + γ + \frac{1}{2 n} + O (\frac{1}{n^{2}}) & (9.21) \end{align}

für $n \to \infty$ , wobei

\begin{array}{l} γ = \int_{1}^{\infty} (\frac{1}{⌊ x ⌋} - \frac{1}{x}) d x = 0.577215664901532 \dots \end{array}

die Euler-Mascheroni-Konstante genannt wird.

Übung 9.63.

Wir wollen die Asymptotik (9.21) in dieser Übung beweisen.

(a): Beweisen Sie, dass das Integral in der Definition von $γ$ konvergiert und dass die Gleichung $\begin{array}{l} \sum_{k = 1}^{n} \frac{1}{k} = \log (n) + γ + \frac{1}{n} - \int_{n}^{\infty} (\frac{1}{⌊ x ⌋} - \frac{1}{x}) d x \end{array}$
für alle $n \in ℕ$ gilt.
(b): Verwenden Sie Taylor-Approximation, um
•
$\log (m + 1) = \log (m) + \frac{1}{m} - \frac{1}{2 m^{2}} + O (\frac{1}{m^{3}})$
•
$\frac{1}{m} - \int_{m}^{m + 1} \frac{1}{t} d t = \frac{1}{2 m^{2}} + O (\frac{1}{m^{3}}) = \frac{1}{2} \int_{m}^{m + 1} t^{- 2} d t + O (\frac{1}{m^{3}})$

für $m \in ℕ$ zu beweisen.
(c): Verwenden Sie das Integralkriterium (Satz 9.35) um zu zeigen, dass $\begin{array}{l} \sum_{m = n}^{\infty} \frac{1}{m^{3}} = O (\frac{1}{n^{2}}) \end{array}$
für $n \to \infty$ .
(d): Verbinden Sie die obigen Aussagen zu einem Beweis von (9.21).
(e): Wiederholen Sie Beispiel 7.5 und approximieren Sie mit der Formel (9.21) die notwendige Anzahl Bausteine $n$ für einen Sprungturm, der $10$ m in den See hinreicht. Vergleichen Sie dies dann zum exakten Resultat $n = 12367$ .