Begründung zur Umschreibung einer Summe zum Logarithmus

30.08.2016, 13:14	Dukha	Auf diesen Beitrag antworten »
Begründung zur Umschreibung einer Summe zum Logarithmus Hallo zusammen, wie kann ich begründen, dass folgendes gilt $\begin{eqnarray} \sum\limits_{k=0}^{n-1} \frac{1}{k+1}=\log(n)+O(1) \end{eqnarray}$ mit $\begin{eqnarray} n\in\mathbb{N} \end{eqnarray}$ Ich habe zunächst gedacht, dass die Taylorformel des Logarithmus helfen könne, doch dies war leider nicht der Fall. Hat jemand einer Idee? Was sollte ich mir genauer anschauen? Danke schonmal!
30.08.2016, 14:48	HAL 9000	Auf diesen Beitrag antworten »
Es ist $\begin{align} \int\limits_1^n \frac{\dd x}{x}=\log(n) \end{align}$ . Versuche deine Summe damit in Beziehung zu setzen - Stichwort: Unter- und Obersummen beim Riemann-Integral.
30.08.2016, 15:47	Dukha	Auf diesen Beitrag antworten »
Danke! Es gilt $\begin{eqnarray} \sum_{k=0}^{n-1} \frac{1}{k+1}=\sum_{k=1}^{n} \frac{1}{k}. \end{eqnarray}$ Die Obersumme deines Integrals ist gerade $\begin{eqnarray} \sum_{k=1}^{n} \frac{1}{k}\ge log(n). \end{eqnarray}$ Wieso erreiche ich nun die Gleichheit, wenn ich $\begin{eqnarray} O(1) \end{eqnarray}$ zur rechten Seite addiere?
30.08.2016, 16:12	HAL 9000	Auf diesen Beitrag antworten »
Wenn du wie empfohlen auch noch eine Untersumme betrachtest, bekommst du auch noch auf der anderen Seite eine Abschätzung, insgesamt dann $\begin{align} \log(n) \leq \sum_{k=1}^n \frac{1}{k} \leq \log(n)+1\qquad () \end{align}$ . Was bedeutet denn gleich nochmal das Landausymbol $\begin{align} O(1) \end{align}$ hier ? Es bedeutet, dass es eine Funktion $\begin{align} g:\;\mathbb{N}\to\mathbb{R} \end{align}$ und eine Zahl $\begin{align} C \end{align}$ mit $\begin{align} \sum_{k=1}^n \frac{1}{k} = \log(n)+g(n) \end{align}$ mit $\begin{align} \|g(n)\|\leq C \end{align}$ für alle $\begin{align} n\in\mathbb{N} \end{align}$ . gibt. Preisfrage: Ist das durch () gewährleistet?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »