261026 Vorlesung

${\lim }_{n\to \infty }\forall ϵ>0\exists N\forall n:n>N:|a_n-g|<ϵ$

${\lim }_{n\to \infty }{a}_n=\infty \forall S\exists N\forall nn>N⟹a_n>S$ monoton wachsen: $\forall n:a_{n+1}\ge a_n$ S ohne Schranke $\forall n:a_n\le S$

Konvergenzverhalten

1. Is $a_n$ monoton wachsen und nach oben beschränkt. Dann ist $a_n$ konvergent (d.h. $\exists$ emdlicher GW)
2. Ist $a_n$ monoton wachsen und nicht nach oben beschränkt, dann ist ${\lim }_{n\to \infty }{a}_n=\infty$
3. $a_n$ monoton fallen und nach unten beschränkt $⟹a_n$ konvergent
4. $a_n$ monoton fallend und nicht beschränkt $⟹{\lim }_{n\to \infty }{a}_n=-\infty$
5. Jede konvergente Folge ist beschränkt

Beweis zu 1.: $a_n$ nach oben beschränkt $⟹\exists$ obere Schranke Sei S kleinste obere Schranke Behauptung: ${\lim }_{n\to \infty }{a}_n=S$

Sei $ϵ>0$ $S-ϵ$ keine obere Schranke, (sonst ist S nicht minimal) $\neg (\forall N:a_n\le S)$ also $\exists N:a_n>S-ϵ$

$\underset{\text{Monotonie}}{\underbrace{⟹}}\forall n:n>N⟹S\cdot ϵ<a_n\le a_n\underset{\text{Beschra¨nktheit}}{\underbrace{\le }}S\le S+ϵ$ $⟹\forall ϵ\exists N\forall n:n>N⟹S-ϵ\le a_n\le S+ϵ$ $⟹{\lim }_{n\to \infty }{a}_n=S$

Beweis zu 2.: $⟹\forall S\in \mathbb{R}:S$ ist keine obere Schranke $⟹\forall S:\neg (\forall N:a_N\le S)$ $⟹\forall S:\exists N:a_N>S$ $\underset{\text{Monotonie}}{\underbrace{⟹}}\forall S\exists N\forall n:\underset{⟹{\lim }_{n\to \infty }{a}_n=\infty }{\underbrace{n>N⟹a_n\ge a_N>S}}$

Beweis zu 3 wie bei 1: GW = größte untere Schranke Beweis zu 4 wie bei 2

Beweis zu 5 $a_n$ konvergent $⟹\exists {\lim }_{n\to \infty }{a}_n=g⟹\forall ϵ\dots$ gilt also auch für $ϵ=1$ $⟹\forall n>N:g-1<a_n<g+1$ $⟹$ obere Schranke $S=max\{a_1,\dots ,a_N,g+1\}$ $⟹$ untere Schranke $S=min\{a_1,\dots ,a_N,g-1\}$

2.6 Die Eulersche Zahl e

Betrachten Folgen $a_n$ und $b_n$ mit $a_n={\left(1+\frac{1}{n}\right)}^n{b}_n={\left(1+\frac{1}{n}\right)}^{n+1}$ für $n\ge 1$

2.6.1 Hilfsmittel (Mittelungleichung)

1. für $x_1,\dots x_m\ge 0$ aus $\mathbb{R}$ gilt $\underset{\text{geometrisches Mittel}}{\underbrace{\sqrt[m]{x_1\cdot x_2\cdot \cdots \cdot x_m}}}\le \underset{\text{arithmetisches Mittel (Durchschnitt)}}{\underbrace{\frac{{\sum }_{k=1}^m{x}_k}{m}}}$
2. Festes $x\ge 0$ aus $\mathbb{R}$ und $n\ge 1$ gilt $\sqrt[n+1]{x^n}\le \frac{1+1nx}{n+1}$ folgt aus 1. $x_{n+1}=1$

Wir wollen die Konvergenz von $a_n\text{ und }{b}_n$ mit Monotonie und Beschränktheit zeigen

2.6.2 Behauptung: $a_n$ ist monoton wachsend

$\left(x=1+\frac{1}{n}\text{ in b}\right)$ einsetzen

$$\begin{array}{rl}& \sqrt[n+1]{{\left(1+\frac{1}{n}\right)}^n}\le \frac{1+n\cdot \left(1+\frac{1}{n}\right)}{n+1}=\frac{1+n+1}{n+1}\\ & \sqrt[n+1]{{\left(1+\frac{1}{n}\right)}^n}\le \frac{1}{n+1}+\frac{n+1}{n+1}=1+\frac{1}{n+1}|({)}^{n+1}\\ & {\left(1+\frac{1}{n}\right)}^n\le {\left(1+\frac{1}{n+1}\right)}^{n+1}\\ & a_n\le a_{n+1}\end{array}$$

2.6.3 Behauptung: $b_n$ ist monoton fallend

beweis ähnlicher allerdings etwas schwerer

2.6.4

$$\begin{array}{rl}& b_n={\left(1+\frac{1}{n}\right)}^{n+1}=\left(1+\frac{1}{n}\right){\left(1+\frac{1}{n}\right)}^n\\ & =\left(1+\frac{1}{n}\right)\cdot a_n>a_n\end{array}$$

2.6.5

$b_1$ ist obere Schranke für $a_n$ $a_1$ ist untere Schranke für $b_n$ $⟹$ beide Folgen monoton und beschränkt, aber konvergent $a_1\underset{2}{\underbrace{\le }}{a}_n\underset{4}{\underbrace{<}}{b}_n\underset{3}{\underbrace{\le }}{b}_1$

Def $e:={\lim }_{n\to \infty }{\left(1+\frac{1}{n}\right)}^n$ Eulersche Zahl Folgerung: ${\lim }_{n\to \infty }{b}_n={\lim }_{n\to \infty }\left(1+\frac{1}{n}\right)\cdot a_n=1\cdot e=e$

• $b_n-a_n=a_n\cdot \left(1+\frac{1}{n}\right)-a_n=\frac{a_n}{n}2<a_n<4$
• $\frac{2}{n}\le b_n-a_n\le \frac{4}{n}$
• $⟹|a_n-e|<\frac{4}{n}$

Bsp.: $a_{500}=2.715e=2.71828\dots$ $|a_{500}-e|\le \frac{4}{500}$

2.6.6 Satz

Ist $x_{n}Folgemit{\lim }_{n\to \infty }{x}_n=\pm \infty$ so ist ${\lim }_{n\to \infty }{\left(1+\frac{1}{x_n}\right)}^{x_n}=e$ Beispiele

2.6.7 Eine schnelle e-Folge

$(S_n)n\ge 1$ $S_n={\sum }_{k=0}^n\frac{1}{k!}$

Damit kann man zeigen, (machen wir aber nicht :) ) $a_n={\left(1+\frac{1}{n}\right)}^n\le S_n\le {\left(1+\frac{1}{n}\right)}^{n+1}=b_n$ $\underset{\text{Sandwich}}{\underbrace{⟹}}{\lim }_{n\to \infty }{s}_n=e$

2.7 Lamdau-Symbolik

2.7.1 Anwendung

1. Laufzeitanalyse von Algorithmen $T(n)$ = Anzahl der Rechenschritte bei Eingabe eines Problems der Größe n $T:\mathbb{N}\to \mathbb{R}$
2. Asymptotische Verhalten von Folgen $a:\mathbb{N}\to \mathbb{R}$ d.h. Verhalten für $n\to \infty$

Beispiel

$$\begin{array}{rl}& T_1=2.79\cdot n^2\\ & T_2=10000\cdot n\\ & T_3=\log n\cdot 50n\\ & T_4=n!\\ & T_5=1.01^n\\ & T_6=n^n\\ & T_2<T_3<T_1<T_5<T_4<T_6\end{array}$$