Define $$H_n := \displaystyle\sum_{k=1}^n \dfrac 1k $$
The problem asks to prove that the map $\phi:\mathbb{N}^\star \longrightarrow \mathbb{N}^\star $ defined by
$$\phi(n) := \lfloor H_n \rfloor $$ is surjective (onto).
I would like to check whether my attempt is correct.
Attempt (induction)
- Base case : $\phi$ takes the values $1$ , $2$.
- Inductive step : $m $ being a natural $\ge 2$, assuming that $\phi$ takes the value $m$ (that is $m=\phi(n)$ for some nonzero natural $n$), we want to show that $\phi$ takes the value $m+1$ as well.
I'm going to use this well-known result as a lemma (without proof)
Lemma : $\forall n \in \mathbb{N}^\star \quad \dfrac 12 \le H_{2n}- H_n < \dfrac 34$
Using the above lemma, we have two cases :
if $m\le H_n < m+\dfrac 12$ then $m+1\le H_{4n} < m+2$ yielding $m+1=\phi(4n)$.
if $m+\dfrac 12 \le H_n < m + 1 $ then $m+1 \le H_{2n} < m + \dfrac 74 < m+2$ yielding $m+1=\phi(2n)$.
In either case, we proved that the value $m+1$ is achieved whenever that the value $m$ is achieved by $\phi$.
That completes our proof by induction if no mistake has been made.
Thanks for any remarks.
Proof without the lemma.
Suppose that the map isn't surjective. Note that $\phi(1) = 1$.
There exists $k\in \mathbb{N}$ such that $$\forall_{n\in \mathbb{N}}\lfloor H_n \rfloor \neq k$$
Since $\phi$ is non-decreasing, we must have $\phi(n)<k<\phi(n+1)$ for some $n$. But then we would have that $\phi(n+1)-\phi(n)\geq 2$, which is impossible. Indeed, $$\phi(n+1)-\phi(n) < H_{n+1}-H_n+1\leq 2.$$