Question

Unlike a decreasing geometric series, the sum of the$\mathbf{1}\mathbf{,}\frac{\mathbf{1}}{\mathbf{2}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{3}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{4}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{5}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{}$ diverges; that is,$\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\frac{\mathbf{1}}{\mathbf{i}}\mathbf{=}\mathbf{\infty }$

It turns out that, for large n , the sum of the first n terms of this series can be well approximated as

$\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\frac{\mathbf{1}}{\mathbf{i}}\mathbf{\approx }\mathbf{In}\mathbf{}\mathbf{n}\mathbf{+}\mathbf{y}$

where is natural logarithm (log base $\mathbf{e}\mathbf{}\mathbf{=}\mathbf{}\mathbf{2}\mathbf{.}\mathbf{718}\mathbf{.}\mathbf{.}\mathbf{.}$) and y is a particular constant $\mathbf{}\mathbf{0}\mathbf{.}\mathbf{57721}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}$. Show that

$\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\frac{\mathbf{1}}{\mathbf{i}}\mathbf{=}\mathbf{\theta }\mathbf{(}\mathbf{log}\mathbf{}\mathbf{n}\mathbf{)}$

(Hint: To show an upper bound, decrease each denominator to the next power of two. For a lower bound, increase each denominator to the next power of 2 .)

Short answer

It is proved that$\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}=\mathrm{\Theta }(\log \mathrm{n})$.

Step-by-step solution

Finding the Upper Bound of the equation

Upper bound:

So, here we are going to expand the given expression$\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}=\infty$

$\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots$

Now, we know that the above expression is lesser than

role="math" localid="1658914247883" $$\begin{gathered} \sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}\le 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\cdots +\frac{1}{2^{\mathrm{k}}}\underset{2^{\mathrm{k}}\mathrm{terms}}{\underbrace{......}}+\frac{1}{2^{\mathrm{k}}}... \\ =\underset{⊝\left(\log \mathrm{n}\right)\mathrm{terms}}{\underbrace{1+1+...+1}}+.... \end{gathered}$$

Because the above sum series is almost equivalent to$\log n$

So, the upper bound is:$(\log n)$

Finding Lower Bound of the equation

Now consider $\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}$, then

$$\begin{gathered} \sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots \\ \le \left(\frac{1}{2}+\frac{1}{2}\right)+\left(\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+...\right) \end{gathered}$$

Now, we know that the above expression is greater than or equal to,$\left(\frac{2}{2}\right)+\left(\frac{4}{4}\right)+\left(\frac{8}{8}\right)+....$ . Then,

$\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}\ge \left(\frac{2}{2}\right)+\left(\frac{4}{4}\right)+\left(\frac{8}{8}\right)+....$

Now, the number of terms in above expression is roughly $\Omega (\log n)$.

role="math" localid="1658914145755" $$\begin{gathered} \sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}\ge \left(\frac{2}{2}\right)+\left(\frac{4}{4}\right)+\left(\frac{8}{8}\right)+.... \\ =\log \mathrm{n} \end{gathered}$$

So, the lower bound is .

From the upper bound and lower bound, we have $\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{1}{\mathrm{i}}=\mathrm{\Theta }(\log \mathrm{n})$.

Hence proved.