I have this math problem that I am stuck on.
Prove by induction on $n$ that $$\sum_{j=1}^{2^n}{\frac{1}{j}>\frac{n}{2}}$$
What I have so far is check for $n=0$ (base case) $\sum_{j=1}^{1}{\frac{1}{j}} = 1 > 0$.
Then I assume $\sum_{j=1}^{2^n}{\frac{1}{j}>\frac{n}{2}}$ is true for all $n\ge 0$.
I then show it is true for $n+1$
$$\sum_{j=1}^{2^{n+1}}{\frac{1}{j}>\frac{n+1}{2}}$$ $$=\sum_{j=1}^{2^{n}}{\frac{1}{j} + \sum_{j=2^n}^{2^{n+1}}{\frac{1}{j}} >\frac{n+1}{2}}$$
$$=\frac{n}{2} + \sum_{j=2^n}^{2^{n+1}}{\frac{1}{j}} >\frac{n+1}{2}$$
$$= \sum_{j=2^n}^{2^{n+1}}{\frac{1}{j}} > \frac{1}{2}$$
I'm stuck here. thanks.
Notice that what you actually need to show is
$$ \sum_{j=2^n+1}^{2^{n+1}}{\frac{1}{j}} > \frac{1}{2} .$$
This follows from the fact that, since
$$\frac{1}{j} \geq \frac{1}{2^{n+1}} \; \text{ for all } j \in \{2^n+1,\dots,2^{n+1}\},$$
with strict inequality for all $j < 2^{n+1}$, then
$$ \sum_{j=2^n+1}^{2^{n+1}}{\frac{1}{j}} > 2^n \frac{1}{2^{n+1}} = \frac{1}{2}.$$