196
$\begingroup$

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.

  • 0
    From [a Harmonic Number page](https://en.wikipedia.org/wiki/Harmonic_number#Arithmetic_properties): "It is well-known that $H_{n}$ is an integer if and only if $n = 1$, a result often attributed to Taeisinger".2017-06-13

10 Answers 10

261

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.

  • 1
    Beautiful! Much nicer than an ugly argument in the style of "writing everything as one fraction, one 'sees' that the denominator has more factors $2$" but essentially the same, though.2014-06-21
61

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

  • 1
    The exact same proof I gave works, just use $2^k$ instead of $p$. Again, you get that the sum is of the form $\frac{1}{2^k}+\frac{a}{b}$, where $b$ (being a divisor of the lcm of stuff divisible by at most $k-1$ copies of 2) is not divisible by $2^k$. This can't be an integer, otherwise $\frac{b}{2^k}+a$ would be an integer, which it isn't.2010-08-18
27

I never heard of the Bertrand postulate approach before. Anton, the argument for the n-th harmonic sum not being an integer when n > 1 goes back to Taeisinger in 1915. In fact, the n-th harmonic sum tends to infinity 2-adically. This 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.

  • 0
    @leonbloy: Thannks, that sounds useful. I'll give it a try...2011-12-06
24

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

See the Example on p. 13 of

http://math.uga.edu/~pete/4400intro.pdf

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.

  • 0
    Could you please provide me the solution using ord(n) ? In the aforementioned text the author says that it's enough to prove that ord(Sn) is never equal to ord (1/(n+1)). But I'm having some troubles in proving this. Thanks a lot! @PeteL.Clark2017-03-22
17

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.

16

I kind of have an elementary solution, it seems to be fine but I am not sure if everything is correct; please point out the mistake(s) I'm making, if any.

Define $H_n:=\sum_{i=1}^n \frac{1}{i}$ Since $0, if $\exists$ some $n$ for which $H_n$ is integral then $H_n=k$ where $0. Then $H_n=k=1+\frac{1}{2}+\frac{1}{3}+\cdots\ +\frac{1}{k}+\cdots\ +\frac{1}{n}\\ \Rightarrow k=\frac{1}{k}+\frac{p}{q}\Rightarrow qk^2-pk-q=0$ where $\gcd(p,q)=1$. Then we get $k=\frac{p\pm \sqrt{p^2+4q^2}}{2q}$ Since $k$ is integer $p^2+4q^2=r^2$ for some $r\in \mathbb{Z}^+$. Let $\gcd(p,2q,r)=d$ and let $\displaystyle x=\frac{p}{d},\ y=\frac{2q}{d},\ z=\frac{r}{d}$. Then $x^2+y^2=z^2$ Now, I make the following claim:

Claim:$p$ is odd and $q$ is even.

Proof: Let $s=2^m\le n$ be the largest power of $2$ in $\{1,2,\cdots,\ n\}$. Then, if $k\ne s$ then the numerator of $\displaystyle \frac{p}{q}$ is the sum of $n-1$ terms out of which one will be odd and hence $p$ is odd. On the other hand, $q$ will have the term $s$ as a factor. So q is even.

Now, if $k=s$, then since $n>2$(otherwise there is nothing to prove)then, there will be a factor $2^{m-1}\ge 2$ in $q$ and one of the sum terms in $p$ that corresponds to $2^{m-1}$ will be odd. Hence in this case also, $p$ is odd and $q$ is even. So the claim is proved. $\Box$

So, now we see that $d\ne 2$ and hence $2|y$. So we have a Pythgorian equation with $2|y, \ x,y,z>0$. hence the solutions will be $x=u^2-v^2,\ y=2uv,\ z=u^2+v^2$ with $(u,v)=1.$ So, since $k$ is positive, $k=\frac{d(x+z)}{dy}=\frac{u}{v}$ But since $(u,v)=1$, $k$ is not an integer (for $n\ge 2$) which is a contradiction. So $H_n$ can not be an integer. $\Box$

  • 0
    I know this is a very late answer, but in the proof of your claim you said that p is the sum of n-1 terms out of which one is odd. Which one is that? And was it really intentional to write the requirement (p,q)=1?2018-08-17
8

Very similar to the Bertrand approach, except significantly more elementary.

Suppose for contradiction that a partial sum of the harmonic series is an integer $z$:

$1 + \frac{1}{2} + \frac{1}{3}+...+\frac{1}{n}=z$

Now consider the maximal power of $2$ below $n$ and let's call it $2^t$. (Note that all other integers between 1 and $n$ have a power of $2$ strictly less than t). Now consider the unique prime factorization of $n!$. The exponent of $2$ in this factorization will be greater than or equal to $2^t$, but instead let us define $M$ as $n!$, except with the power of $2$ in its prime factorization set to be $t-1$ (as opposed to some integer greater than $t$).

Multiply both sides of the equation by $M$:

$M+\frac{M}{2}+\frac{M}{3}+...+\frac{M}{2^t}+...+\frac{M}{n}=Mz$

$M$ has enough factors to make all terms on the LHS integers except for the $\frac{M}{2^t}$ term. Summing the LHS, we see that is not an integer, even though the RHS is an integer. Contradiction, QED.

This proof is essentially the same as the proof with Bertrand's postulate, except with $2^t$ instead of a prime number $p$ between $\frac{n}{2}$ and $n$.

  • 1
    This same approach was already described in several other answers.2015-07-29
4

A more general approach that includes the proof using the prime 2 but is valid for any prime $ (posted elsewhere with an erroneous n! instead of LCD): Let the least common denominator of the harmonic series H(n) be LCD(n). Take any prime p in the sequence 1 to n and let q be the highest power of p so that $p^q ≤ n$.

For any k, $1 ≤k ≤n $, LCD(n)/k is an integer and = 0 (mod p) except $LCD(n)/p^q$ which is an integer and does not contain p, and therefore cannot be 0 (mod p). But H(n)LCD(n)=0 (mod p) (since LCD(n) contains the factor p), a contradiction if H(n) is an integer.

(The simplicity comes from the use of a complicated LCD(n) which exists but whose prime powers I would not be able to describe in the general case).

2

if we consider highest prime upto $n$ then given sum can be written as $1/p + a/b$ where a is some integer $b$ is also an integer not divisible by $p$. so $b/p$ can not be an integer and so $b/p + a$. so the given sum can not an integer

  • 0
    You might want to use MathJax. The simple way to use it is to surround your math with \$. There are some commands you might need to learn.2015-10-15
2

Here's a short proof: Let $H_n = \displaystyle \sum_{k=1}^n\dfrac{1}{k}.$ One can show that $\displaystyle\sum_{k=1}^{n}\dfrac{(-1)^{k-1}\binom{n}{k}}{k}= H_n.$ This can be rewritten as: $\sum_{k=0}^{n}{(-1)^k\binom{n}{k}a_k} = b_n$

where $a_0 =0$ and $a_i = \dfrac{1}{i}$ for $i=1,\ldots n$ and $b_n = -H_n$

This answer shows that the $b_i$ are integers if and only if the $a_i$ are integers. Clearly for $i \geq 2 $ we can see that the $a_i$ are not integers, from which it follows that neither are the $b_i, i\geq 2.$