Prove this inequality: $\frac n2 \le \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac1{2^n - 1} \le n$ $\dfrac{n}{2} \le \dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{2^n - 1} \le n $
I've Tried for hours but didn't got any striking idea. I don't have any efforts to show rather than induction. Please Try If you 've non-inductive proof.
 A: HINT: Induction on $n$ really is the easiest way to go. Note that 
$$\frac1{2^{n+1}-1}=\frac1{2^n+(2^n-1)}\;,$$
so there are $2^n$ terms in the expression
$$\frac1{2^n}+\frac1{2^n+1}+\ldots+\frac1{2^{n+1}-1}\;.$$
Now use the fact that each term is between $\dfrac1{2^{n+1}}$ and $\dfrac1{2^n}$.
For a non-inductive argument you could look at Riemann sums over subintervals of width $1$. If 
$$S_n=\sum_{k=1}^{2^n-1}\frac1k\;,$$
show that
$$\int_1^{2^n}\frac{dx}x=n\ln 2\le S_n\le 1+\int_1^{2^n-1}\frac{dx}x=1+\ln(2^n-1)\;,$$
and use this to get the desired result. You’ll have to show that $1+\ln(2^n-1)\le n$ and that $n\ln 2\ge\dfrac{n}2$.
A: It's a standard trick. Let
$$
H_n = 1 + \frac12 +\ldots+ \frac1n.
$$
Look on $H_{2^n-1}$:
$$
n=1: H_1 = 1=1\\
n=2: H_3 = 1 + \frac12 + \frac13 < 1 + \frac12 + \frac12 = 1 + 1=2\\
n=3: H_7 = 1 + \frac12 + \frac13 + \left(\frac14+\frac15+\frac16+\frac17\right) < 1 + \frac{2}{2} + \left(\frac14+\frac14+\frac14+\frac14\right)=1 + 2 =3
$$
So, $H_{2^n-1} < n$. Analogously,
$$
n=1: H_1 = 1=1\\
n=2: H_3 = 1 + \frac12 + \frac13 > 1 + \frac14 + \frac14 = 1 + \frac{1}{2}\\
n=3: H_7 = 1 + \frac12 + \frac13 + \left(\frac14+\frac15+\frac16+\frac17\right) > 1 + \frac{1}{2} + \left(\frac18+\frac18+\frac18+\frac18\right)=1 + \frac{2}{2},
$$
or in general
$$
H_{2^n-1}>1 + \frac{n-1}{2} = \frac{n+1}{2}
$$
A: $H_m = 1 + 1/2 + 1/3 + ... + 1/m$
$\ln (m) < H_m < \ln (m + 1)$
put $m = 2^n - 1 $
$n/2 \leq \ln (2^n - 1)$
$\ln (2^n -1) + 1 \leq n $
A: as a curiosity we may develop an approximation for the sum under consideration as a special case of a recondite formula cited by Brian Scott  in this answer
according to wikipedia 
$$
H_n = \ln n+\gamma+\frac1{2n}-\frac1{12n^2} + \frac1{120n^4} - \epsilon \tag{1}
$$
where $0 \lt \epsilon \lt \frac1{252n^6}$
for $n \gt 0$ we have:
$$
\log (2^n-1) = n \log 2 +\log (1 -2^{-n}) = n \log 2 - 2^{-n} - 2^{-(2n+1)} -R
$$
where $0 \lt R \lt 2^{-(3n+1)}$
also
$$
\frac1{2(2^n-1)} = 2^{-(n+1)}+ 2^{-(2n+1)} + R'
$$
where $0 \lt R' \lt 2^{-3n}$
and finally taking only the first term in the expansion of $\frac{2^{-2n}}{12(1-2^{-n})^2}$  we obtain the approximation:
$$
H_{2^n-1} \approx 0.69314718... n -\frac13(2^{-(n+1)}+\frac32)^2 + 1.32721566...
$$
btw, the wikipedia article cited is worth a browse - it contains some mind-boggling stuff! including this little gem:
$$
\int_0^{\infty} e^{-x} \log^2 x dx = \gamma^2 + \frac{\pi^2}6
$$
