Prove that $\frac{n}{2}$ < 1 + $\frac{1}{2}$ + $\frac{1}{3}$ + ... + $\frac{1}{2^n-1}$ < n for every n $\in \Bbb{N}$, n > 1, by using induction.

Question

The basis checks out, and if we assume that the statement holds for n, we have to prove that it also holds for $n+1$:

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

Now I've split the middle part into the sum of: 1 + $\frac{1}{2}$ + $\frac{1}{3}$ + ... + $\frac{1}{2^n-1}$ (which is defined in the assumption) and $\frac{1}{2^n}$ + $\frac{1}{2^n+1}$ + ... + $\frac{1}{2^{n+1}-1}$ .

But I don't know what to do from here on out.. If someone could show me a detailed answer i'd be really thankful, since this is my first time dealing with induction

Answer 1

Prove that $\frac{n}2<1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n-1}<n$ for all $n\in\mathbb {N}$, $n>1$

$P_r:=\sum_{a=1}^{2^r-1} \frac{1}{a}$

$P_{n}=1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n-1}$

Base Case:

$n=2\\P_2=1+\frac{1}2+\frac{1}3\approx1.83$

Now, $\frac{2}2<P_2<2$ (True)

Inductive Hypothesis:

let assume, $\frac{m}2 \le P_{m} \le m$ is true where $m>1$ and $m\in \mathbb{N}$.

Inductive Step:

$$\therefore P_{m+1}{= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^m-1} + \frac{1}{2^m}+\frac{1}{2^m+1}+\dots+\frac{1}{2^{m+1}-1}\\ = P_{m}+ \underbrace{\frac{1}{2^m}+\frac{1}{2^m+1}+\dots+\frac{1}{2^{m+1}-1}}_{2^m \text{terms}} \\ \geq \frac{m}{2} + 2^m\cdot\frac{1}{2^{m+1}} \quad (\, \because \frac{1}{2^{m+1}}<\text{ any one of $2^m$ terms })\\ =\frac{m+1}{2}}$$

Similarly,

$$P_{m+1}{= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^m-1} + \frac{1}{2^m}+\frac{1}{2^m+1}+\dots+\frac{1}{2^{m+1}-1}\\ = P_{m}+ \underbrace{\frac{1}{2^m}+\frac{1}{2^m+1}+\dots+\frac{1}{2^{m+1}-1}}_{2^m \text{terms}} \\ \leq m + 2^m\cdot\frac{1}{2^{m}}\quad (\, \because \frac{1}{2^{m}}\ge\text{ any one of $2^m$ terms })\\ =m+1}$$

$\therefore \frac{(m+1)}2 \le P_{m+1} \le (m+1)$

Conclusion:

$P_{m+1}$ is true when $P_m$ is true.

Thus, by the Principle of Mathematical Induction, the inequality is valid for all $n>1$ integers.

---

Discussion:

1. The most complex line in the proof is number of terms. We have a problem in that we have the terms from $\frac{1} {2^m}$ to $\frac{1} {2^{m+1}-1}$ to deal with, and we don’t know how many of them there are. Let’s look at the powers of $2$ as they increase: $${2^0 = 1\\ 2^1 = 2 = 1 + 1\\ 2^2 = 4 = 2 + 2\\ 2^3 = 8 = 4 + 4\\ 2^4 = 16 = 8 + 8\\ 2^5 = 32 = 16 + 16}$$ The “distance” on the numberline from a power of $2$ to the next power is always the same as the previous power of $2$. That is, to get from $2^k$ to $2^{k+1}$ we need $2^k$ terms.

2. The minimum value among the terms $\frac{1}{2^m} + \frac{1}{2^m + 1} + \dots + \frac{1}{2^{m+1}-1}$ occurs at $\frac{1}{2^{m+1}-1}$, which is greater than $\frac{1}{2^{m+1}}$. If we substitute each of the $2^m$ terms with $\frac{1}{2^{m+1}}$, the resulting sum will always be smaller than the original. Similarly, the maximum value among the terms $\frac{1}{2^m} + \frac{1}{2^m + 1} + \dots + \frac{1}{2^{m+1}-1}$ occurs at $\frac{1}{2^m}$. If we substitute each of the $2^m$ terms with $\frac{1}{2^{m}}$, the resulting sum will always be greater than the original.

Answer 2

Hint: $$\frac{1}{2^n}+\frac{1}{2^n+1}+\dots+\frac{1}{2^{n+1}-1} \leq \frac{2^n}{2^{n}}$$ (Count the number of terms from $2^n$ to $2^{n+1}-1$ and the greatest element among $\frac{1}{2^n}$,$\dots$, $\frac{1}{2^{n+1}-1}$).

Also

$$\frac{2^n}{2^{n+1}} < \frac{2^n}{2^{n+1}-1} \leq \frac{1}{2^n}+\frac{1}{2^n+1}+\dots+ \frac{1}{2^{n+1}-1}$$ (Now the least element among $\frac{1}{2^n}$,$\dots$, $\frac{1}{2^{n+1}-1}$.