Prove: $\sum\limits_{j=1}^{2^n}\frac{1}{j} \geq 1 + \frac{n}{2}$ for all positive integers $n$.

Question

Given the following proof.

Proof: by induction on n

Base Case: $n = 1$ is trivial. Done

Inductive Step: suppose for $n \geq 1$ we have $\sum\limits_{j=1}^{2^n}\frac{1}{j} \geq 1 + \frac{n}{2}$. We show for $n + 1$. Observe $$ \begin{equation} \begin{split} (1)& \quad\sum_{j=1}^{2^{n+1}}\frac{1}{j} &= \sum_{j=1}^{2^n} \frac{1}{j} + \sum_{j=2^n + 1}^{2^{n+1}}\frac{1}{j} \\ (2)&&\geq 1 + \frac{n}{2} + \left(2^{n+1} - 2^n\right)\frac{1}{2^{n+1}} \\ &&= 1 + \frac{n}{2} + 1 - \frac{1}{2} \\ &&= 1 + \frac{n+1}{2} \end{split} \end{equation} $$ Done.

Two questions: How does the procedure of separating the summation of the LHS in (1) to the two summands on the RHS in (1) work? In addition, how does one evaluate $\sum\limits_{j=2^n + 1}^{2^{n+1}} \frac{1}{j}$ to be the third summand in (2)?

NOTE: The summations limits in second summand of the RHS of (1) may be wrong. I could not remember fully, what it was.

In addition, I am NOT asking why we separate in (1) to prove. I am asking how the algebraic manipulations works in going from LHS of (1) to RHS of (1).

Answer 1

First question: Notice: $\sum_{k=1}^{M} a_k= a_1 + a_2 + ........ + a_{M-1}+a_M =$

$\underbrace{a_1 + a_2 + ...+ a_W} + \underbrace{a_{W+1}+..... + a_{M-1}+a_M}=$

$\sum_{k=1}^{W} a_k + \sum_{k=W+1}^{M} a_k$.

We can split any sum anywhere that way.

Second question:

If $2^{n}+1 \le j \le 2^{n+1}$ then

$\frac 1{2^{n} + 1} \ge \frac 1j \ge \frac 1{2^{n+1}}$ so

$\frac 1j \ge \frac 1{2^{n+1}}$

SO $\sum_{j=2^n+1}^{2^{n+1}} \frac 1j \ge \sum_{j=2^n+1}^{2^{n+1}} \frac 1{2^{n+1}}=$

$\underbrace{\frac 1{2^{n+1}}+\frac 1{2^{n+1}}+\frac 1{2^{n+1}}+ .... + \frac 1{2^{n+1}}}_{(2^{n+1} - 2^n)\text{ times}}=$

$(2^{n+1} - 2^n)\frac 1{2^{n+1}}=$

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

Answer 2

As the number of summations is finite, you can break the summation from any point you desire. Hence, it is straightforward to reach RHS (1) from LHS (1).

For the second part of your question it is easy to replace $\frac{1}{j}$ with minimum value in the range of summation $\frac{1}{2^{n+1}}$. Therefore,

$$\sum_{j = 2^n + 1}^{2^{n+1}}\frac{1}{j} > \frac{1}{2^{n+1}}\sum_{j = 2^n + 1}^{2^{n+1}}1 = (2^{n+1} - (2^n + 1) + 1)\frac{1}{2^{n+1}} = (2^{n+1} - 2^n)\frac{1}{2^{n+1}}$$.