<s>[INST] 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.
 [/INST] 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}
$$
</s>