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

Solution 1:

Hint $\ $ Since there is a unique denominator $\rm\:\color{#C00} {2^K}\:$ having maximal power of $2,\,$ upon multiplying all terms through by $\rm\:2^{K-1}$ one deduces the contradiction that $\rm\ 1/2\, =\, c/d \;$ with $\rm\: d \:$ odd, $ $ e.g.

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

The prior sum has all odd denominators so reduces to a fraction with odd denominator $\rm\,d\, |\, 3\cdot 5\cdot 7$.

Note $\ $ I purposely avoided any use of valuation theory because Anton requested an "elementary" solution. The above proof can easily be made comprehensible to a high-school student.

Solution 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}}$.

Solution 3:

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 at here.

Solution 4:

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.