Asymptotische "Abschätzung" einer Summe (Landau)

17.08.2013, 22:59

toneesnightmare

Asymptotische "Abschätzung" einer Summe (Landau)

Meine Frage:
Hallo,

warum gilt:

$\begin{eqnarray*} \sum_{i<j} \frac{2}{i} = O( log(j) ) \end{eqnarray*}$

Meine Ideen:
Naja, ich summiere immer kleinere Werte auf

$\begin{eqnarray*} \sum_{i<j} \frac{2}{i} = O( \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{j-1} ) \end{eqnarray*}$

Ich kann mir grob vorstellen, dass dies immer weiter wächst und dabei aber immer langsamer wächst. Also genauso wie die Logarithmus-Funktion.
Aber reicht das als Argumentation?
Und warum der Logarithmus von j?

18.08.2013, 00:10

HAL 9000

Auf diesen Beitrag antworten »

Bei Symbolik $\begin{eqnarray*} \sum_{i<j} \frac{2}{i} \end{eqnarray*}$ weiß man gar nicht so richtig, was hier der Summationsindex ist, aus dem mutmaßlichen Ergebnis ist aber zu vermuten, dass du damit $\begin{eqnarray*} \sum_{i=1}^{j-1} \frac{2}{i} \end{eqnarray*}$ meinst. Und das kann man (exklusive des ersten Summanden für $\begin{eqnarray*} i=1 \end{eqnarray*}$ ) als Untersumme des Integrals $\begin{eqnarray*} \int\limits_1^{j-1} \frac{2}{x} ~ \dd x \end{eqnarray*}$ ansehen, d.h.

$\begin{eqnarray*} \sum_{i=1}^{j-1} \frac{2}{i} = 2 + \sum_{i=2}^{j-1} \frac{2}{i} \leq 2 + \int\limits_1^{j-1} \frac{2}{x} ~ \dd x = 2 + 2\ln(j-1) \end{eqnarray*}$ für $\begin{eqnarray*} j\geq 2 \end{eqnarray*}$ .

Und die rechte Seite ist zweifelsohne $\begin{eqnarray*} O(\ln(j)) \end{eqnarray*}$ . Es geht auch nicht "kleiner", da die fragliche Summe auch Obersumme von $\begin{eqnarray*} \int\limits_1^j \frac{2}{x} ~ \dd x \end{eqnarray*}$ ist, d.h.

$\begin{eqnarray*} \sum_{i=1}^{j-1} \frac{2}{i} \geq \int\limits_1^j \frac{2}{x} ~ \dd x = 2\ln(j) \end{eqnarray*}$ .

19.08.2013, 03:03

toneesnightmare

Auf diesen Beitrag antworten »

Vielen Danke für deine Antwort!

Bei Interesse von Personen die diesen Eintrag noch lesen werde,
hier ein Link für den von dir beschriebenen Zusammenhang:
http://en.wikipedia.org/wiki/Summation#A...inite_integrals

Die Integrale passen in meine Vorstellung noch rein, aber das die Summe genau dazwischen sein soll muss ich mir nochmal genauer anschauen.

Zitat:

Bei Symbolik $\begin{eqnarray*} \sum_{i<j} \frac{2}{i} \end{eqnarray*}$ weiß man gar nicht so richtig, was hier der Summationsindex ist,

In meinem Skript steht leider auch nicht vielmehr. Ist ein Informatiker-Skript, vielleicht deshalb Big Laugh

. Man kann nur von $\begin{eqnarray*} i \end{eqnarray*}$ und $\begin{eqnarray*} j \end{eqnarray*}$ aus $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ ausgehen.

Deine Antwort hilft mir sehr fürs Verständnis, wobei ich schon aber fast denke, dass sie zu ausführlich für meine Zwecke ist.

Danke und Gruß

19.08.2013, 08:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von toneesnightmare
Deine Antwort hilft mir sehr fürs Verständnis, wobei ich schon aber fast denke, dass sie zu ausführlich für meine Zwecke ist.

Meistens gehen die Beschwerden in die andere Richtung, d.h., dass zu wenig erklärt wird. Big Laugh

Neue Frage »

Antworten »

Asymptotische "Abschätzung" einer Summe (Landau)

Verwandte Themen