Sigma index (Induction)

Question

I was wondering how the index that's left is measured. When you prove this via induction, $$\sum_{k=1}^{2^n} \frac{1}{k} \geq \frac{n}{2} $$ $$\sum_{k=1}^{2^{n+1}} \frac{1}{k}= \sum_{k=1}^{2^{n}} \frac{1}{k} + \sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k} $$ you will come across this part $$\geq\frac{n}{2}+\sum_{k=2^n+ 1}^{2^{n+1}} \frac{1}{k}\geq \frac{n}{2}+2^n\cdot \frac{1}{2^{n+1}}$$ where does the $2^n$ comes from? Is it a index difference?

Answer 1

Yes, it depends on the limits of the sum. More generally, if $(x_k)_{k\geq 1}$ is a decreasing sequence then, for $b\geq a\geq 1$, $$\sum_{k=a+1}^bx_k\geq \sum_{k=a+1}^bx_b=x_b\sum_{k=a+1}^b1=(b-a)\cdot x_b.$$ In your case, $x_k=1/k$, $b=2^{n+1}$, and $a=2^n$. Therefore $$(b-a)=2^{n+1}-2^n=2^n.$$