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}.$ 
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.
 A: 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}$$
A: 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}$$
A: 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.
