# 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.

• Hint: $$1 + \underbrace{\frac12 + \frac12} + \underbrace{\frac14 + \frac14 + \frac14 + \frac14} + \ldots$$ Jul 19, 2015 at 6:49
• Sorry couldn't get it. Jul 19, 2015 at 6:51
• Also, I think it helps to know that $2^n-1=1+2+\cdots+2^{n-1}$. Jul 19, 2015 at 6:52
• @SolidSnake Yes, I know that But how it 'll help ? Jul 19, 2015 at 6:59
• @martycohen: This question was posted on th 19th of July. The one that you reference was asked "9 hours ago". Which is the duplicate of which, then? I shall flag the other one and vote to leave this open. Aug 21, 2015 at 14:11

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$.

• Good answer Brian, although I think O.P. wants a non-inductive proof. Jul 19, 2015 at 6:54
• @SolidSnake: Clearly the OP would prefer one, but experience says that other arguments may not be unwelcome. Also, including other arguments makes the question more valuable as a reference for users other than the OP. However, I’ve added a sketch of a non-inductive argument. Jul 19, 2015 at 7:09
• Great! I agree, your answer is perfectly fine and it adds a different argument that solves the problem. Thanks for the edit. (I was not the downvoter BTW). Jul 19, 2015 at 7:11
• It would be great answer, I accept it, but I don't know such higher mathematics, I'm a 11th grade student learning inequalities. I'm curious about different methods of problem solving, I'm not intelligent enough to find such methods, but I believe each idea has some meaning like idea about non--inductive proof. So, I've put my 'emotions' on this website. @BrianM.Scott given non-inductive proof but i can't get it. But does any elementary non-inductive proof exists ? Jul 19, 2015 at 7:30
• @user91374: I’ve been trying to think of one, but so far without any luck. Jul 19, 2015 at 7:31

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}$$

• Note that this, if carried out rigorously, is also an induction argument. Jul 19, 2015 at 7:07
• @BrianM.Scott, I don't agreed. It can be prove by induction. But also you can note that $\frac1x > \frac{1}{2^n}$ if $x<2^n$; so, it's direct evaluation of lower bound for sum Jul 19, 2015 at 7:09
• I’m afraid not. If it’s written out in detail, it’s an induction argument. It’s just that the induction step is so obvious that it’s easy not to realize this. Jul 19, 2015 at 7:11
• @BrianM.Scott, ok, $$\sum_{i=1}^{2^n-1} a_n = \sum_{k=0}^n\sum_{i=2^{k}}^{2^{k+1}-1}$$ Is it induction? Even if so, it's "indirect" induction)) Jul 19, 2015 at 7:18
• I agree with @BrianM.Scott Jul 19, 2015 at 7:31

$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$

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$$