0 Daumen
496 Aufrufe

Aufgabe:

Zeigen Sie, dass fur die Funktion ¨ f(n) := i=1n1/i \sum\limits_{i=1}^{n}{1/i}
die Beziehung f(n) ∈ Θ(log(n)) gilt.


Problem/Ansatz: Hallo , ich konnte praktisch (mit Graph) beweisen, dass es zwei reelle Zahlen c1,c2 und eine natürliche Zahl n0 geben , sodass die ungleichung für n ≥ n0  c1.log(n)≤ f(n) ≤ c2.log(n) gilt , aber wie kann man es theoretisch beweisen

Danke im Voraus für eure Hilfe

Avatar von

3 Antworten

0 Daumen

Wir schreiben mal f(n)=i=1n1i1f(n)=\sum\limits_{i=1}^n \frac1i\cdot 1, dann nimm nochmal den Graphen von x1xx\mapsto\frac1x zur Hand und erkenne, dass 1i1\frac1i\cdot 1 der Flächeninhalt eines Rechtecks unter oder über dem Graphen ist. Aufsummieren gibt einen Flächeninhalt unter bzw. der Kurve (bisschen aufpassen, Kleinigkeiten sind noch zu beachten). Damit kannst Du die Summe in Beziehung setzen zu einem Integral...

Avatar von 10 k
0 Daumen

Hallo

Schätze ab mit der Ober und Untersumme  1n1/xdx \int\limits_{1}^{n} 1/xdx mit Schrittweite 1

Gruß lul

Avatar von 108 k 🚀
0 Daumen

Aloha :)

Plotlux öffnen

f1(x) = 1/x·(x>1)·(x<7)Zoom: x(0…8) y(0…1,1)f2(x) = 1·(x>1)·(x<2)+1/2·(x>2)·(x<3)+1/3·(x>3)·(x<4)+1/4·(x>4)·(x<5)+1/5·(x>5)·(x<6)+1/6·(x>6)·(x<7)f3(x) = 1·(x>1)·(x<2)+1/(x-1)·(x>2)·(x<7)

Aus der Grafik entnehmen wir:1n+11xdx<i=1n1i1+2n+11x1dx{\color{blue}\int\limits_1^{n+1}\frac1x\,dx}<\red{\sum\limits_{i=1}^n\frac1i}\le\green{1+\int\limits_2^{n+1}\frac{1}{x-1}\,dx}Wir bestimmen die Integrale und erhalten:[ln(x)]1n+1<i=1n1i1+[ln(x)]2n+1\left[\ln(x)\right]_{1}^{n+1}<\sum\limits_{i=1}^n\frac1i\le1+\left[\ln(x)\right]_2^{n+1}ln(n+1)<i=1n1i1+ln(n+1)ln(2)<1+ln(n+1)\ln(n+1)<\sum\limits_{i=1}^n\frac1i\le1+\ln(n+1)-\ln(2)<1+\ln(n+1)Daher ist   i=1n1iθ(ln(n))\;\sum\limits_{i=1}^n\frac1i\in\theta(\ln(n)).

Avatar von 152 k 🚀

Ein anderes Problem?

Stell deine Frage