Prove that $n/2 < 1/1 + 1/2 +1/3 + 1/4 +1/5 + 1/6 + ... + 1/2^{n-1} \le n$. n is a natural ,$n \ge 1$. Induction.

Question

I tried to prove 2 of the sides seperately.

i = n/2
ii = 1/1 + 1/2+1/3 + 1/4 +1/5 + 1/6 + ... 1/2^n-1
iii= n

We can prove ii =< iii by:

Base case: n=1
1/2-1 =< 1 is true

Hypothesis: assume ii=<iii is true

Induction:
1/1+1/2+...+(1/2^n-1) + 1/2^n*2-1 < n+1

Since we have proven ii =< iii,we are left with:
1/2^n*2-1 < 1
Since the smallest possible value for n is 1,it follows that this is true for any k>n.

I have no idea how to prove i<ii however. 
Any advice? Am i making any mistakes?

Answer 1

Hint: The sum $\dfrac{1}{2^{n-1}+1}+\dfrac{1}{2^{n-1}+2}+ \cdots + \dfrac{1}{2^n-1} + \dfrac{1}{2^n}$ has $2^{n-1}$ terms, each of which is between $\dfrac{1}{2^n}$ and $\dfrac{1}{2^{n-1}}$. Thus, we can bound $$\dfrac{1}{2} = 2^{n-1} \cdot \dfrac{1}{2^n} \le \dfrac{1}{2^{n-1}+1}+\dfrac{1}{2^{n-1}+2}+ \cdots + \dfrac{1}{2^n-1} + \dfrac{1}{2^n} \le 2^{n-1} \cdot \dfrac{1}{2^{n-1}} = 1.$$

Can you see how to use this to complete the inductive step?

Answer 2

The proposition is ambiguous

$\frac {n}{2}<\sum_\limits{k=1}^{n-1} \frac 1{2^{k}} <n$ is not true

$\frac {n}{2}<\sum_\limits{k=1}^{2^{n-1}} \frac 1{k} <n$ might be

Going with the second...

This fact might help.

$\frac 12 = \frac {2^{n-1}}{2^{n}}<\sum_\limits{k=2^{n-1}+1}^{2^{n}} \frac 1k<\frac {2^{n-1}}{2^{n-1}} = 1$

For each term $\frac {1}{2^{n}}\le \frac 1k < \frac {1}{2^{n-1}}$ and there are $2^{n-1}$ terms.