Prove that $1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{2^n-1}<n$ for $n\geq{2}$

Question

I tried using mathematical induction to prove this, but the problem I faced was that there are a lot of numbers between $\frac{1}{2^k-1}$ and $\frac{1}{2^{k+1}-1}$. Is it possible to prove this with induction or is there a better method?

Answer 1

Given the hints above, we have during the induction process that

$$\frac{1}{2^n}+\frac{1}{2^n+1}+\frac{1}{2^n+2}+...+\frac{1}{2^{n+1}-1}<1$$

If we multiply both sides by $2^n$ and note that there are $2^n$ terms being added, we have that

\begin{eqnarray*} \frac{2^n}{2^n}+\frac{2^n}{2^n+1}+\frac{2^n}{2^n+2}+...+\frac{2^n}{2^{n+1}-1}&<&2^n\\1+\frac{2^n+1-1}{2^n+1}+\frac{2^n+2-2}{2^n+2}+...+\frac{2^n+(2^n-1)-(2^n-1)}{2^{n}+2^n-1}&<&2^n \\1+1-\frac{1}{2^n+1}+1-\frac{2}{2^n+2}+...+1-\frac{2^n-1}{2^{n+1}-1}&<&2^n\\2^n-\frac{1}{2^n+1}-\frac{2}{2^n+2}-...-\frac{2^n-1}{2^{n+1}-1}&<&2^n\\-\left(\frac{1}{2^n+1}+\frac{2}{2^n+2}+...+\frac{2^n-1}{2^{n+1}-1}\right)&<&0 \end{eqnarray*}

which is true for all $n\ge2$

Answer 2

HINT: Try a proof by induction. In your inductive step, subract $n=k$ from $n=k+1$ for this expression: $$\sum_{r=2^k}^{2^{k+1}-1}{\frac 1r}<1$$ See if you can resolve this.

Answer 3

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{2^n-1}\approx \int_{2}^{2^n} \frac{1}{k-1}dk$$$$ = ln(2^n-1) = S < ln(2^n) =nln2 =0.693147n<n$$ for $n\geq{2}$

Hence proved

Answer 4

$$ 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{2^n-1}=1+\left(\frac{1}{2^1}+\frac{1}{2^2-1}\right)+\left(\frac{1}{2^2}+\cdots+\frac{1}{2^3-1}\right)+\cdots+\left(\frac{1}{2^{n-1}}+\cdots+\frac{1}{2^n-1}\right)<n, $$ since $$ \frac{1}{2^{k-1}}+\cdots+\frac{1}{2^k-1}<2^{k-1}\cdot\frac{1}{2^{k-1}}=1. $$