Upper and lower bounds for $S(n) = \sum_{i=1}^{2^{n}-1} \frac{1}{i} = 1+\frac{1}{2}+ \cdots +\frac{1}{2^n-1}.$

Question

For a positive integer $n$ let $S(n) = \sum_{i=1}^{2^{n}-1} \frac 1i = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+ \cdots +\frac{1}{2^n-1}.$

Then which of the following are true.

• (a) $S(100)\leq 100$.
• (b) $S(100)>100$.
• (c) $S(200)\leq 100$.
• (d) $S(200)>100$.

My attempt

• For the upper bound $$\begin{align} S(n) &= 1 + \left( \frac 12 + \frac 13 \right) + \left( \frac 14 + \frac 15 + \frac 16 + \frac 17 \right) + \cdots + \left( \frac 1{2^{n-1}} + \frac 1{2^{n-1}+1} + \cdots + \frac 1{2^n-1} \right) \\ &< 1 + \left( \frac 12 + \frac 12 \right) + \left( \frac 14 + \frac 14 + \frac 14 + \frac 14 \right) + \cdots + \left( \frac 1{2^{n-1}} + \frac 1{2^{n-1}} + \cdots + \frac 1{2^{n-1}} \right) \\ &= \underbrace{1 + 1 + \cdots + 1}_{n\text{ times}} \\ &= n. \end{align}$$

  So we get $S(n) < n$ (for $n > 1$), and in particular $S(100) < 100$.

Now I did not understand how to calculate a lower bound, or if there is any other method by which we can solve this.

Answer 1

Yes, there is another method that is easy to implement. Recall that we have

$$\int_1^N \frac{1}{x}\,dx<\sum_{k=1}^N\frac1k <1+\int_1^N \frac{1}{x}\,dx$$

For $N=2^n-1$ this gives

$$\log (2^n-1)<\sum_{k=1}^{2^n-1}\frac1k <1+\log (2^n-1)$$

Then, $\log (2^n-1)=n\log 2+\log (1-2^{-n})$ and therefore, we can write

$$n\log(2)-\frac{1}{2^n-1}<\log (2^n-1)<1+n\log 2-2^{-n}$$

For purposes of approximating for $n=100$, we have

$$69<100\,\log (2)-\frac{1}{2^{100}-1}<\sum_{k=1}^{2^{100}-1}\frac1k <1+100\,\log (2)-2^{-100}<71$$

so that

$$\bbox[5px,border:2px solid #C0A000]{69<\sum_{k=1}^{2^{100}-1}\frac1k <71}$$

For $n=200$, we have

$$138<200\,\log (2)-\frac{1}{2^{200}-1}<\sum_{k=1}^{2^{200}-1}\frac1k <1+100\,\log (2)-2^{-200}<140$$

so that

$$\bbox[5px,border:2px solid #C0A000]{138<\sum_{k=1}^{2^{200}-1}\frac1k <140}$$

Answer 2

Group the terms exactly as you have, but get a lower bound that can be easily manipulated.

I'll copy, paste, and edit your equations to show what I mean.

$$\displaystyle S(n) = 1+\underbrace{\frac{1}{2}+\frac{1}{3}}+\underbrace{\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}}+....+\underbrace{\frac{1}{2^{n-1}}+..+\frac{1}{2^n-1}}\\ >1+\underbrace{\frac{1}{4}+\frac{1}{4}}+\underbrace{\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}}+....+\underbrace{\frac{1}{2^{n}}+..+\frac{1}{2^{n}}}\\ =1+\frac12+\frac12....(\bf{n-times}) = 1+\frac{n}{2}$$

So we get $$\displaystyle S(n) = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+..........+\frac{1}{2^n-1} >1+\frac{n}{2}$$

Answer 3

This is not an answer but it is too long for a comment.

Since $$S(n)=\sum_{i=1}^{2^n-1}\frac 1i=H_{2^n-1}$$ you could be interested by this paper in which the author, Mark B. Villarino, developed extremely sharp bounds for the harmonic numbers.

The first and simplest set of bounds (Theorem $1$) is given by $$\frac{1}{2 m+\frac{1}{1-\gamma }-2}+\log (m)+\gamma\leq H_m \lt \frac{1}{2 m+\frac{1}{3}}+\log (m)+\gamma$$

Applied to the cases given by Dr. MV, the bounds coincide to more than $50$ significant figures.