Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
It is a very strange phenomenon that many problem books seem to push the Bertrand's Postulate solution to this problem. I remember that this came up as a problem (apropos of nothing) in my freshman year math class, and I had some problem book at hand and duly turned in a solution which used BP. The next year I got the problem in a number theory course and by then was sophisticated enough to see the elementary solution involving the ord_2 function. –  Pete L. Clark Aug 19 '10 at 0:04
    
Note that I include this exercise as a -- not fully worked out -- example in my (relatively advanced) undergraduate number theory course. See the example on page 13 of math.uga.edu/~pete/4400intro.pdf. (I should admit that a lot of the students have trouble with the corresponding homework problem that asks the details to be filled in.) –  Pete L. Clark Aug 19 '10 at 0:05
1  
@Pete: that's interesting. In high school competition math circles the 2-adic proof is very well known. I first learned it on the AoPS website but it is probably also in some competition book. –  Qiaochu Yuan Aug 19 '10 at 2:07

6 Answers 6

up vote 93 down vote accepted

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.

share|improve this answer
4  
Bill, this is a great answer. In particular, your example makes the proof crystal clear. The use of colors is also very good by the way. +1 –  Adrián Barquero Jun 25 '12 at 21:01
    
did you try to show for $n=7$? –  Une Femme Douce Jul 31 '13 at 4:22
    
I am not able to understand how to use your hint for general $n$ –  Une Femme Douce Jul 31 '13 at 4:26
    
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. –  barto Jun 21 at 15:17

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

share|improve this answer
    
It would probably be a good idea to flesh this out a little. –  Qiaochu Yuan Aug 18 '10 at 22:58
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. –  Anton Geraschenko Aug 18 '10 at 23:00

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.

share|improve this answer
1  
@Pete: But your exposition uses valuation theory - which disqualifies it as "elementary". Obviously the problem is trivial to anyone knowing valuation theory.Namely the sum has a lone dominant term with $v_2 < 0$ so, by the domination principle, the sum has $v_2 < 0$ so is nonintegral. –  Bill Dubuque Aug 19 '10 at 0:36
7  
@BD: The construction uses something that happens to be a valuation, but I don't think that makes it valuation theory. The definition of ord-p uses nothing more or less than the fundamental theorem of arithmetic, so is appropriate in an introductory course. The point of this exercise is to get students used to making arguments of this kind which -- if they continue on in their study of number theory -- will be seen to be valuation-theoretic. (Anyway the argument can certainly be phrased without using ord-2 if that's your taste.) –  Pete L. Clark Aug 19 '10 at 2:49
    
By the way, the fact that each partial sum has a unique term of minimal 2-adic valuation was not so easy for my students. That's most of the exercise that I left for them to solve, and for many it was challenging, not trivial. –  Pete L. Clark Aug 19 '10 at 2:53
    
@Pete: Certainly it can be presented at an elementary level, and there is no doubt that it is instructive to do so. However, it's a lot of overhead to introduce for a single problem - as here. It's puzzling to hear that the exercise proved difficult for some students. Did you give them prior examples of employing the dominance principle? E.g. that a set of integers having precisely one odd element has odd sum (that is precisely what occurs in the sum above if one multiplies it through by a 2-least common denominator). –  Bill Dubuque Aug 19 '10 at 3:17
1  
Hi BS, I understand your point. But I think, in this kind of forum, this type of answer have a great value. Altought Anton asked for simple proof, the Pete's argument help the interested students to learn most power techniques in simple situation. @Thanks Pete for the link. –  Leandro Aug 19 '10 at 3:25

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.

share|improve this answer
10  
+1: a new blurb. If there were a listserve that would automatically notify me whenever there is a new blurb from KCd, I would gladly sign up for it! –  Pete L. Clark Aug 19 '10 at 3:56
2  
@PeteL.Clark : You can create a feed for a webpage with pagee2rrss.com. In this case, add to you feeds reader: page2rss.com/rss/2b74436a91d372fca18b5f1645f1d59e –  leonbloy Dec 5 '11 at 19:58
    
@leonbloy: Thannks, that sounds useful. I'll give it a try... –  Pete L. Clark Dec 6 '11 at 4:01

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.

share|improve this answer
    
+1 for the reference to Ireland and Rosen. –  Old John Jun 25 '12 at 20:57

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<H_n<n$, if $\exists$ some $n$ for which $H_n$ is integral then $H_n=k$ where $0<k<n$. 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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.