5
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ Hint: $$ 1 + \underbrace{\frac12 + \frac12} + \underbrace{\frac14 + \frac14 + \frac14 + \frac14} + \ldots $$ $\endgroup$ Jul 19, 2015 at 6:49
  • $\begingroup$ Sorry couldn't get it. $\endgroup$ Jul 19, 2015 at 6:51
  • $\begingroup$ Also, I think it helps to know that $2^n-1=1+2+\cdots+2^{n-1}$. $\endgroup$
    – Daniel
    Jul 19, 2015 at 6:52
  • $\begingroup$ @SolidSnake Yes, I know that But how it 'll help ? $\endgroup$ Jul 19, 2015 at 6:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – Alex M.
    Aug 21, 2015 at 14:11

4 Answers 4

9
$\begingroup$

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

$\endgroup$
8
  • 2
    $\begingroup$ Good answer Brian, although I think O.P. wants a non-inductive proof. $\endgroup$
    – Daniel
    Jul 19, 2015 at 6:54
  • $\begingroup$ @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. $\endgroup$ Jul 19, 2015 at 7:09
  • $\begingroup$ 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). $\endgroup$
    – Daniel
    Jul 19, 2015 at 7:11
  • $\begingroup$ 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 ? $\endgroup$ Jul 19, 2015 at 7:30
  • $\begingroup$ @user91374: I’ve been trying to think of one, but so far without any luck. $\endgroup$ Jul 19, 2015 at 7:31
4
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ Note that this, if carried out rigorously, is also an induction argument. $\endgroup$ Jul 19, 2015 at 7:07
  • $\begingroup$ @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 $\endgroup$ Jul 19, 2015 at 7:09
  • $\begingroup$ 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. $\endgroup$ Jul 19, 2015 at 7:11
  • $\begingroup$ @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)) $\endgroup$ Jul 19, 2015 at 7:18
  • $\begingroup$ I agree with @BrianM.Scott $\endgroup$ Jul 19, 2015 at 7:31
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .