Show that for all Harmonic numbers $H(k)$, the inequality $H(2^k) \leq 1 + k$ holds for all natural numbers.

Question

Hi so the question is prove that for all harmonic numbers $$H(k) = 1 + \frac{1}{2} + \frac13 + \dotsb + \frac{1}{k}$$ the inequality $H(2^k) \leq 1 + k$ holds for all natural numbers. I'm not going to put my entire answer here but was wondering if someone could tell me if I'm on the right track.

So I got this far:
Say $H(2^k) = k + 1$ and $$H(2^{k+1}) = k + 1 + 2^k \frac{1}{2^{k+1}} = k + 1 + \frac{1}{2} = k + \frac{3}{2}$$ and $k + \frac{3}{2} \leq 1 + (k + 1)$

Is this correct or at least am I on the right track??

Answer 1

Yes, you're on the right track, but it seems that you've mixed something in the inductive step. In each "step" by going from $H(2^k)$ to $H(2^{k+1})$ you add $2^k$ new numbers, each of which is less than $\frac{1}{2^k}$, so the difference between $H(2^k)$ and $H(2^{k+1})$is always going to be less than $1$. Con you continue now?

Answer 2

Let us prove something stronger through a powerful technique, creative telescoping.
We may recall that since in a neighbourhood of the origin we have $$ \text{arctanh}(x) = \frac{1}{2}\log\left(\frac{1+x}{1-x}\right)=x+\frac{x^3}{3}+\frac{x^5}{5}+\frac{x^7}{7}+\ldots\tag{1} $$ the inequality $$ \frac{1}{n}\leq 2\,\text{arctanh}\left(\frac{1}{2n}\right) = \log\left(\frac{2n+1}{2n-1}\right) = \frac{1}{n}+\frac{1}{12n^3}+\frac{1}{80n^5}+\ldots \tag{2}$$ surely holds for any $n\geq 1$. Additionally, $\log\left(\frac{2n+1}{2n-1}\right)$ is a telescopic term, wonderful: $$ \color{red}{H_N} = \sum_{n=1}^{N}\frac{1}{n}\color{red}{\leq} \sum_{n=1}^{N}\log\left(\frac{2n+1}{2n-1}\right) = \color{red}{\log(2N+1)}\leq \log(N)+1\tag{3} $$ In particular, $H_{2^k}\leq 1+k\log 2$.

---

The super-tight inequality $$ \log\left(N+\frac{1}{2}\right)+\gamma \leq H_N \leq \log\left(N+\frac{1}{2}\right)+\gamma+\frac{1}{24 N(N+1)} \tag{4}$$ where $\gamma$ is the Euler-Mascheroni constant can be proved through the same technique.

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

By Induction !!!:

\begin{align} H_{2^{k + 1}} & = \sum_{n = 1}^{2\ \times\ 2^{k}}{1 \over n} = \sum_{n = 1}^{2^{k}}{1 \over n} + \sum_{n = 2^{k} + 1}^{2\ \times\ 2^{k}}{1 \over n} < \pars{1 + k} + {1 \over 2^{k} + 1}\pars{2 \times 2^{k} - 2^{k}} = \pars{1 + k} + {2^{k} \over 2^{k} + 1} \\[5mm] & < \bbx{1 + \pars{k + 1}} \end{align}