4

I think it is equivalent to prove that $f(p)=E(1+\frac{1}2+\frac{1}{3} \ldots+\frac{1}{p})$ is surjective, but I have no idea how to prove it.

But here is what I did: $$f(2n)-f(n)=\frac{1}{n+1}+\ldots+\frac{1}{2n},$$ so $f(2^n)-1\ge \frac{1}{2}n.$

Hence, $f(2^{2n})\ge1+n>n$.

amWhy
  • 209,954
user600785
  • 520

3 Answers3

6

You are almost there. You showed that there exist $m\in\Bbb N$ with $f(m)\ge n+1$ (namely, for $m=2^{2n}$).

Now let $m$ be the smallest natural with $f(m)\ge n+1$. Then certainly $m>1$. Hence $f(m-1)$ is defined and - by minimality of $m$ - not $\ge n+1$, i..e, $f(m-1)<n+1$. On the other hand $f(m-1)=f(m)-\frac 1m\ge n+1-\frac 1m>n$

Hagen von Eitzen
  • 374,180
  • So the $p$ in the title is $p = m-1$?. It might be simpler to let$m= p$ be the smallest so that $f(p)> n$ (with strict inequality). Then $f(p-1) \le n < f(p) = f(p-1) + \frac 1p < n + 1$. – fleablood Oct 06 '18 at 01:05
3

If we consider the partial sums of the harmonic series, $H_n=\sum_{k=1}^{n}\frac{1}{k}$, we get an increasing and divergent sequence, but $H_{n+1}-H_n$ is always $\leq\frac{1}{2}$. If we consider the intervals $$ U_1=[H_1=1,2),\quad U_2=[2,3),\quad U_3=[3,4),\quad \ldots $$ we have that the elements of $\{H_n\}_{n\geq 1}$ cannot skip any of these intervals, since that would imply $H_{m+1}-H_m\geq 1$ for some $m\geq 1$ (a "leap").
In particular there is a harmonic number in each interval, as was to be shown.

A reasonable alternative is to prove the claim "by hand" for small values of $n$, then exploit the fact that $H_p = \log(p)+\gamma+O\left(\frac{1}{p}\right)$, hence in $U_N$ there are approximately $0.964745628\,e^N\gg 1$ harmonic numbers for any $N$ large enough.

Jack D'Aurizio
  • 353,855
  • It turns out you don't need to do any proving "by hand" in the alternative if you're careful with the asymptotic estimates: if $N>1$, the quantity $n$ of harmonic numbers $H_i$ such that $N<H_i\leq N+\tfrac{74}{75}$ can be shown to satisfy $n>(8/3)^{(N-1)}$. – K B Dave Oct 06 '18 at 03:02
0

I'm lazy and I like to take well-known tools and pound them with hammers.

It's known that the harmonic series, $\sum_{k=1}^{\infty} \frac 1k$ diverges and you seem to have proven that adequately.

So that's my tool.... that and the standard definition of "diverge": So for $n$ there exists a $m$ so that $\sum_{k=1}^m \frac 1k > n$.

Let $p$ be the least such integer (Well-ordered principal if I have to keep pointing out my tools) we have $n < \sum_{k=1}^{p} \frac 1k$ and assuming $p> 1$ (which it must be if $n \ge 1=\sum_{k=1}^1 \frac 1k$) then $p-1$ does not have the property so $\sum_{k=1}^{p-1} \frac 1k \le n <\sum_{k=1}^{p} \frac 1k$.

And as long as I'm naming my tools sum indexing and inequality axioms gives me:

$\sum_{k=1}^{p-1} \frac 1k \le n \le \sum_{k =1}^{p}\frac 1k=(\sum_{k=1}^{p-1} \frac 1k) + \frac 1p <( \sum_{k=1}^{p-1} \frac 1k) + 1 < n + 1$

fleablood
  • 124,253