Is there an elementary proof that $\sum \limits_{k=1}^n \frac1k$ is never an integer?

Question

If $n>1$ is an integer, then $\sum \limits_{k=1}^n \frac1k$ is not an integer.

If you know Bertrand's Postulate, then you know there must be a prime $p$ between $n/2$ and $n$, so $\frac 1p$ appears in the sum, but $\frac{1}{2p}$ does not. Aside from $\frac 1p$, every other term $\frac 1k$ has $k$ divisible only by primes smaller than $p$. We can combine all those terms to get $\sum_{k=1}^n\frac 1k = \frac 1p + \frac ab$, where $b$ is not divisible by $p$. If this were an integer, then (multiplying by $b$) $\frac bp +a$ would also be an integer, which it isn't since $b$ isn't divisible by $p$.

Does anybody know an elementary proof of this which doesn't rely on Bertrand's Postulate? For a while, I was convinced I'd seen one, but now I'm starting to suspect whatever argument I saw was wrong.

Answer 1

Hint $ $ There is a $\rm\color{darkorange}{unique}$ denominator $\rm\,\color{#0a0} {2^K}$ having maximal power of $\:\!2,\,$ so scaling by $\rm\,\color{#c00}{2^{K-1}}$ we deduce a contradiction $\large \rm\, \frac{1}2 = \frac{c}d \,$ with odd $\rm\,d \:$ (vs. $\,\rm d = 2c),\,$ e.g.

$$\begin{eqnarray} & &\rm\ \ \ \ \color{0a0}{m} &=&\ \ 1 &+& \frac{1}{2} &+& \frac{1}{3} &+&\, \color{#0a0}{\frac{1}{4}} &+& \frac{1}{5} &+& \frac{1}{6} &+& \frac{1}{7} \\ &\Rightarrow\ &\rm\ \ \color{#c00}{2}\:\!m &=&\ \ 2 &+&\ 1 &+& \frac{2}{3} &+&\, \color{#0a0}{\frac{1}{2}} &+& \frac{2}{5} &+& \frac{1}{3} &+& \frac{2}{7}^\phantom{M^M}\\ &\Rightarrow\ & -\color{#0a0}{\frac{1}{2}}\ \ &=&\ \ 2 &+&\ 1 &+& \frac{2}{3} &-&\rm \color{#c00}{2}\:\!m &+& \frac{2}{5} &+& \frac{1}{3} &+& \frac{2}{7}^\phantom{M^M} \end{eqnarray}$$

All denom's in the prior fractions are odd so they sum to fraction with odd denom $\rm\,d\, |\, 3\cdot 5\cdot 7$.

Note $ $ Said $\rm\color{darkorange}{uniqueness}$ has easy proof: if $\rm\:j\:\! 2^K$ is in the interval $\rm\,[1,n]\,$ then so too is $\,\rm \color{#0a0}{2^K}\! \le\, j\:\!2^K.\,$ But if $\,\rm j\ge 2\,$ then the interval contains $\rm\,2^{K+1}\!= 2\cdot\! 2^K\! \le j\:\!2^K,\,$ contra maximality of $\,\rm K$.

The argument is more naturally expressed using valuation theory, but I purposely avoided that because Anton requested an "elementary" solution. The above proof can easily be made comprehensible to a high-school student.

See the Remark here for a trickier application of the same idea (from a contest problem).

Answer 2

An elementary proof uses the following fact:

If $2^s$ is the highest power of $2$ in the set $S = \{1,2,...,n\}$, then $2^s$ is not a divisor of any other integer in $S$.

To use that,

consider the highest power of $2$ which divides $n!$. Say that is $t$.

Now the number can be rewritten as

$\displaystyle \frac{\sum \limits_{k=1}^{n}{\frac{n!}{k}}}{n!}$

The highest power of $2$ which divides the denominator is $t$.

Now the highest power of $2$ that divides $\displaystyle \frac{n!}{k}$ is at least $t-s$. If $k \neq 2^{s}$, then this is atleast $t-s+1$ as the highest power of $2$ that divides $k$ is atmost $s-1$.

In case $k=2^s$, the highest power of $2$ that divides $ \dfrac{n!}{k}$ is exactly $t-s$.

Thus the highest power of $2$ that divides the numerator is atmost $t-s$. If $s \gt 0$ (which is true if $n \gt 1$), we are done.

In fact the above proof shows that the number is of the form $\frac{\text{odd}}{\text{even}}$.

Answer 3

What the heck -- I'll leave my comment as an answer.

See the Example on p. 13

This is discussed, together with (as a footnote) the strange phenomenon that this is often solved by an appeal to Bertrand's Postulate. The discussion in the above text is intended to be "didactic" in that a few details are left to the reader, and I recommend it as a good exercise to flesh them out.

Answer 4

I never heard of the Bertrand postulate approach before, although it turns out that the first proof that the $n$-th harmonic sum is not an integer when $n > 1$ uses Bertrand's postulate and determinants. It appeared in a paper of Theisinger (Bemerkung über die harmonische Reihe, Monatsh. f. Mathematik und Physik 26 (1915), 132--134) that you can read here and he refers to Bertrand's postulate as Chebyshev's theorem. (Update: in several places I have seen Theisinger misspelled as Taesinger, and I am guilty of doing that myself in this answer until I corrected it.) The 2-adic proof is due to Kürschák (A Harmonikus Sorról, Mat. és Fiz. Lapok, 27 (1918), 299--300) and you read it here.

I like to think of this result as saying the $n$-th harmonic sum tends to infinity $2$-adically. That naturally raises the question of the $p$-adic behavior of harmonic sums for odd primes $p$, which quickly leads into unsolved problems. I wrote a discussion of that here.

Answer 5

This is a h.w. problem in Ch 1 of "Ireland and Rosen" - prob 30. There is a hint on p. 367. Let $s$ be the largest integer such that $2^s \le n$, and consider:

$\sum \limits_{k=1}^n \frac{2^{s - 1}}k$

Show that this sum can be written in the form $a/b$ + $1/2$ with $b$ odd.

Then apply problem 29 which is:

Suppose $a, b, c, d$ in $\mathbb{Z}$ and $gcd (a,b) = (c,d) = 1$

If $(a/b) + (c/d)$ = an integer, then $b = \pm d$. (But $b$ odd, $d$ = $2$.)

Maybe this was part and parcel of earlier answers. If so forgive me for trying.