Question

(Requires calculus) Let${\mathit{H}}_{\mathbf{n}}$ be the nth harmonic number

${\mathit{H}}_{\mathbf{n}}\mathbf{=}\mathbf{1}\mathbf{+}\frac{\mathbf{1}}{\mathbf{2}}\mathbf{+}\frac{\mathbf{1}}{\mathbf{3}}\mathbf{+}\mathbf{\dots }\mathbf{.}\mathbf{.}\mathbf{+}\frac{\mathbf{1}}{\mathbf{n}}$

Show that${\mathit{H}}_{\mathbf{n}}\mathbf{\text{is}}\mathbf{O}\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{)}$.[Hint: First establish the inequality $\mathbf{\sum }_{\mathbf{j}\mathbf{=}\mathbf{2}}^{\mathbf{n}}\mathbf{ }\frac{\mathbf{1}}{\mathbf{j}}\mathbf{<}{\mathbf{\int }}_{\mathbf{1}}^{\mathbf{n}}\mathbf{ }\frac{\mathbf{1}}{\mathbf{x}}\mathit{d}\mathit{x}$by showing that the sum of the areas of the rectangle of height $\frac{\mathbf{l}}{\mathbf{j}}$with base form $\mathit{j}\mathbf{-}\mathbf{1}\mathbf{\text{to}}\mathit{j}\mathbf{,}\mathbf{\text{for}}\mathit{j}\mathbf{=}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathit{n}$is less than the area under the curve $\mathit{y}\mathbf{=}\frac{\mathbf{1}}{\mathbf{x}}$from 2 to n].

Short answer

Using the sum of the areas of the rectangle, it is proved that $H_n\text{is}O(\log n)\text{for}k=3$ and$C=\frac{2}{\log e}$ .

Step-by-step solution

Establishing the inequality for the sum of the areas of the rectangle:

Since, $H_n$is decreasing when n > 0 ,

Area of the rectangle with the height$\frac{1}{k}$ and base form j - 1$\to$j less than the area under the curve$y=\frac{1}{k}$ with the same base

$\begin{array}{r}\frac{1}{j}(j-(j-1\left)\right)<{\int }_{j-1}^j \frac{1}{x}dx\\ \Rightarrow \frac{1}{j}<{\int }_{j-1}^j \frac{1}{x}dx\end{array}$

Now, since our harmonic function extends to n.

Therefore, we have to take the sum of either side for j = 2,3,...,n

$\begin{array}{r}\sum _{j=2}^n \frac{1}{j}<\sum _{j=2}^n {\int }_{j=1}^j \frac{1}{x}dx\\ \Rightarrow \sum _{j=2}^n \frac{1}{j}<{\int }_1^n \frac{1}{x}dx\\ \Rightarrow 1+\sum _{j=2}^n \frac{1}{j}<1+{\int }_1^n \frac{1}{x}dx\end{array}$

Simplifying the obtained inequality:

Since,

$H_n\le 1+{\int }_1^n \frac{1}{x}dx$

We can write it as,

$\begin{array}{r}{H}_n\le 1+{\left.(\ln x)\right|}_1^n\\ \Rightarrow 1+\ln n-\ln 1\\ \Rightarrow 1+\ln n\end{array}$

If$n>3\text{, the}1\le \ln n$

$\begin{array}{r}{H}_n\le \ln n+\ln n\\ H_n\le 2\ln n\text{for}n>3\\ H_n\le \frac{2\log n}{\log e}\text{for}n>3\\ \left|H_n\right|\le \frac{2}{\log e}\cdot |\log n|\\ \Rightarrow \left|f\right(n\left)\right|\le \frac{2}{\log e}\left|g\right(n\left)\right|\end{array}$

Hence, it is proved that is .$H_n\text{is}O(\log n)\text{for}k=3\text{and}C=\frac{2}{\log e}\text{.}$