Explanation of part of a particular proof by induction that the harmonic series diverges

Question

One proof by induction that a harmonic series diverges begins $\sum_{j=1}^{2^{n+1}}\frac{1}{j}>\frac{(n+1)+1}{2}=\frac{n+2}{2}$ so: $$\begin{aligned}\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}>\sum_{j=1}^{2^{n}}\frac{1}{j}+\sum_{j=2^{n}+1}^{2^{n+1}}\Bigl(\frac{1}{2}\Bigr)^{n+1}\\ &=\sum_{j=1}^{2^{n}}\frac{1}{j}+\Bigl(\frac{1}{2}\Bigr)^{n+1}\biggl[\sum_{j=2^{n}+1}^{2^{n+1}}1\biggr]>\sum_{j=1}^{2^{n}}\frac{1}{j}+\Bigl(\frac{1}{2}\Bigr)^{n+1}\bigl[2^{n+1}-(2^n+1)+1\bigr]\\ &=\sum_{j=1}^{2^{n}}\frac{1}{j}+\biggl[1-\frac{1}{2}\biggr]\end{aligned}$$ Screenshot of the full proof

I follow the basis of the proof by comparison but not the algebra in these first few steps. Could someone write/explain them more simply? Thanks!

P.S. To be clear, I am not looking for an explanation of the proof per se but rather of these steps of this particular proof.

Answer 1

The first step is breaking up the sum from $j=1$ to $j=2^{n+1}$ into two chunks, from $j=1$ to $j=2^n$, and from $j=2^n+1$ to $j=2^{n+1}$. We do nothing with the first chunk. The second chunk is

$$\frac1{2^n+1}+\frac1{2^n+2}+\ldots+\frac1{2^{n+1}}\;,\tag{1}$$

and the smallest term in this sum is the last one, because it has the biggest denominator. Now $2^{n+1}=2\cdot2^n$, so $\frac1{2^{n+1}}=\frac1{2^n+2^n}$; this makes it easy to see that there are $2^n$ terms in $(1)$. There are $2^n$ terms, and each of them is at least as big as the last one, which is $\frac1{2^{n+1}}=\left(\frac12\right)^{n+1}$. Moreover, some of them are larger than $\frac1{2^{n+1}}$, so the sum in $(1)$ is bigger than

$$2^n\cdot\left(\frac12\right)^{n+1}=2^n\cdot\frac1{2^{n+1}}=\frac12\;,$$

and therefore

$$\sum_{j=1}^{2^n}\frac1j+\sum_{j=2^n+1}^{2^{n+1}}\frac1j>\sum_{j=1}^{2^n}\frac1j+\frac12\;.$$

Your source is carrying out essentially this same calculation, but organizing it a little differently and presenting it very differently. The first inequality in the computation is justified by the fact that $$\frac1j\ge\frac1{2^{n+1}}=\left(\frac12\right)^{n+1}$$ whenever $2^n+1\le j\le 2^{n+1}$, with equality only when $j=2^{n+1}$. The equality that immediately follows it is just factoring out the constant term $\left(\frac12\right)^{n+1}$, leaving behind a factor of $1$ in each term of the second summation. The new second summation, $\sum_{j=2^n+1}^{2^{n+1}}1$ just counts the terms in $(1)$. The last term has $j=2^{n+1}$, and the first has $j=2^n+1$, so there are $2^{n+1}-2^n$ terms, and $\left(\frac12\right)^{n+1}(2^{n+1}-2^n)=1-\frac12=\frac12$.

Answer 2

$\begin{aligned}\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} >\sum_{j=1}^{2^{n}}\frac{1}{j}+\sum_{j=2^{n}+1}^{2^{n+1}}\Bigl(\frac{1}{2}\Bigr)^{n+1} ---(1)\\(2)--- &=\sum_{j=1}^{2^{n}}\frac{1}{j}+\Bigl(\frac{1}{2}\Bigr)^{n+1}\biggl[\sum_{j=2^{n}+1}^{2^{n+1}}1\biggr]>\sum_{j=1}^{2^{n}}\frac{1}{j}+\Bigl(\frac{1}{2}\Bigr)^{n+1}\bigl[2^{n+1}-(2^n+1)+1\bigr]---(3)\\ &=\sum_{j=1}^{2^{n}}\frac{1}{j}+\biggl[1-\frac{1}{2}\biggr]\end{aligned}$

in $(1)$, the sum has been taken from $1$ to $2^n$ and the remaining terms till the next power of $2$, $2^{n+1}$ and the inequality follows from the fact that for each $j$ satisfying $2^{n+1}>j>2^n$, $$\dfrac1j>\dfrac1{2^{n+1}} \text{ and taking sum in the interval specified above}\\ \implies \sum_{j=2^n+1}^{2^{n+1}-1} \dfrac1j>\sum_{j=2^n+1}^{2^{n+1}-1} \dfrac1{2^{n+1}} \\ \implies \sum_{j=2^n+1}^{2^{n+1}-1} \dfrac1j + \dfrac1{2^{n+1}} >\sum_{j=2^n+1}^{2^{n+1}-1} \dfrac1{2^{n+1}} + \dfrac1{2^{n+1}} \\ \implies \sum_{j=2^n+1}^{2^{n+1}} \dfrac1j>\sum_{j=2^n+1}^{2^{n+1}} \dfrac1{2^{n+1}} = \sum_{j=2^n+1}^{2^{n+1}} \left(\dfrac12\right)^{n+1} ---(4) $$ which justfies the inequality in $(1)$.

The equality in $(2)$ follows by taking $\left(\dfrac12 \right)^{n+1}$ common from the sum in $(4)$ since it does not depend upon the index of summation $j$.

The inequality sign $\gt$ between $(2)$ and $(3)$ should be an equality because $$\left(\sum_{j=2^n+1}^{2^{n+1}} 1 \right)\text{ counts the number of numbers from } 2^n+1 \text{ to } 2^{n+1}$$ which is precisely $2^{n+1}-(2^n+1)+1$ [the number of integers from integers $a$ to $b$ counting both of them, with $a\le b$ is $b-a+1$]