諧波系列的大θ表示法

Question

我想證明諧波系列的大θ表示法是θ（logn）。 我想用積分來表示。

我正在試圖在方式來顯示這一點：在這種方式它不工作

**ln(n)=integral [1 to n] dx/x <= sum k=1 to n of 1/k <= 1 + integral [2 to n] dx/x = 1 + ln(n)** 

，怎麼一回事，因爲在「1」我不能證明諧波系列緊bounde是THETA（LOGN） 。

我該如何展示這一點，併爲了克服這個障礙？ 請幫忙。

謝謝你們。

Answer 1

獲得界限的一個好方法是對總和中的每個術語應用估計......上限估計或下限估計。例如：

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8> = 1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8

然後，將（1/4 + 1/4）= 1/2和組（1/8 + 1/8 + 1/8 + 1/8）= 1/2並繼續。你最終得到1/2「的次數的總和。」多少次？好吧，log_2（n）多次 - 我會讓你找出原因。

您可以用類似的方式得到高估，或者更簡單的方法是使用積分。請注意，在[n，n + 1]範圍內x爲1 /（x-1）> = 1/n。

因此1 + 1/2 + 1/3 + 1/4 + ... + 1/n < = 1 +從2到n 1 /（x-1）dx的積分）。