Inequality with the $2^n$ partial sum of the 'harmonic series'

Question

I would like to know whether $p_n:=\sum\limits_{k=1}^{2^n}\frac{1}{k}\le n+1$ for all $n\in\mathbb{N}\setminus\{0\}$ holds or not.

It holds for $n=1,2,3$. Furthermore computing $p_n$ for $n$ big the graph looks similar to the graph of the log-function. On the other hand on the left site of the inequality we have 2^n-summand whereas on the right hand site we have just n+1. Thus I'm not quite sure intuitively if this can be proven (then it can be done by induction) or disproven. Formally, the induction step: $$p_{n+1}=p_n+\frac{1}{2^n+1}+\frac{1}{2^n+2}+\cdots+\frac{1}{2^{n+1}}\le ( n+1)+ \frac{1}{2^n+1}+\frac{1}{2^n+2}+\cdots+\frac{1}{2^{n+1}} $$leads to check if $\frac{1}{2^n+1}+\frac{1}{2^n+2}+\cdots+\frac{1}{2^{n+1}} \le1$ holds. Here I'm stuck.

Answer 1

You’re adding $2^n$ terms, each of which is at most $\frac1{2^n+1}$, so

$$\sum_{k=1}^{2^n}\frac1{2^n+k}\le 2^n\cdot\frac1{2^n+1}=\frac{2^n}{2^n+1}<1\;.$$

Answer 2

Indeed, the induction step is correct. You have

$$\frac{1}{2^n +1} + \frac{1}{2^n +2}+ \ldots + \frac{1}{2^{n+1}} \leq \frac{1}{2^n +1} + \ldots + \frac{1}{2^n +1} \leq \frac{2^n}{2^n +1},$$ where in the last step we used the fact that there are $2^n$ terms in the sum. Since $\frac{2^n}{2^n +1}\leq 1,$ the proof folows by induction.