Proof by induction of the Inequality of Harmonic numbers: $H_{2^n} \ge 1+ \frac n2$

Question

My question is, for the question below, in the inductive step, where does $\dfrac{1}{2^{(k+1)}}$ come from?And where does $2^k$ come from in the third last step?

Answer 1

the $1/2^{k+1}$ comes in because that's what the $2^{k+1}$-th term would be (they want to prove the inequality for $H_{2^{k+1}}$). The $2^k$ on the third to last line comes in by them saying that $$\frac{1}{2^k+1}+\frac{1}{2^k+2}+\ldots+\frac{1}{2^{k+1}}\ge \frac{1}{2^{k+1}}+\frac{1}{2^{k+1}}+\ldots+\frac{1}{2^{k+1}}.$$ Going from $2^k+1$ to $2^{k+1}$, there are $2^k$ terms. And so the right hand side of the inequality (i.e. the third line from the bottom) simplifies to $2^k\cdot\frac{1}{2^{k+1}}$.

Answer 2

Because there are $2^k$ terms, each at least $\frac1{2^{k+1}}$.

These terms are $\frac1{2^k+1}$, $\frac1{2^k+2}$, $\frac1{2^k+3}$, ..., $\frac1{2^{k}+2^k}=\frac1{2^{k+1}}$.