Beziehung von Funktion f(n) zeigen , ¨ f(n) := \sum\limits_{i=1}^{n}{1/i}

Question

Aufgabe:

Zeigen Sie, dass fur die Funktion ¨ f(n) := \( \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

Answer 1

Wir schreiben mal \(f(n)=\sum\limits_{i=1}^n \frac1i\cdot 1\), dann nimm nochmal den Graphen von \(x\mapsto\frac1x\) zur Hand und erkenne, dass \(\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...

Answer 2

Hallo

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

Gruß lul

Answer 3

Aloha :)

~plot~ 1/x*(x>1)*(x<7) ; [[0|8|0|1,1]] ; 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) ; 1*(x>1)*(x<2)+1/(x-1)*(x>2)*(x<7) ~plot~

Aus der Grafik entnehmen wir:$${\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:$$\left[\ln(x)\right]_{1}^{n+1}<\sum\limits_{i=1}^n\frac1i\le1+\left[\ln(x)\right]_2^{n+1}$$$$\ln(n+1)<\sum\limits_{i=1}^n\frac1i\le1+\ln(n+1)-\ln(2)<1+\ln(n+1)$$Daher ist \(\;\sum\limits_{i=1}^n\frac1i\in\theta(\ln(n))\).