# Harmonic Numbers

• August 6th 2010, 10:24 PM
melese
Harmonic Numbers
Challange Problem; for those who have never seen it, try this by yourselves.

Prove that for $n>1$, the sum $\displaystyle{1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}}$ is not an integer.

Moderator approved CB
• August 6th 2010, 10:46 PM
Also sprach Zarathustra
Maybe a solution: (first thing that came to my head...)

1+1/2+...+1/n=H_n

Hence:

H_n - H_{n-1}=1/n

n(H_n - H_{n-1})=1

Suppose H_n integer, hence H_n - H_{n-1} not integer! BUT n(H_n - H_{n-1}) is integer (1) ==>H_n can't be integer.
• August 6th 2010, 11:10 PM
melese
Quote:

Originally Posted by Also sprach Zarathustra
Maybe a solution: (first thing that came to my head...)

1+1/2+...+1/n=H_n

Hence:

H_n - H_{n-1}=1/n

n(H_n - H_{n-1})=1

Suppose H_n integer, hence H_n - H_{n-1} not integer! BUT n(H_n - H_{n-1}) is integer (1) ==>H_n can't be integer.

Hi Also sprach Zarathustra, you're are saying essentially that the product of an integer and a rational (that is non-integer) cannot be an integer.
To look at differently $H_n-H_{n-1}$ is indeed not an integer ( $1/n)$, and also $n(H_n-H_{n-1} )=n\cdot\frac{1}{n}=1$.
• August 7th 2010, 08:21 AM
tonio
Quote:

Originally Posted by Also sprach Zarathustra
Maybe a solution: (first thing that came to my head...)

1+1/2+...+1/n=H_n

Hence:

H_n - H_{n-1}=1/n

n(H_n - H_{n-1})=1

Suppose H_n integer, hence H_n - H_{n-1} not integer! BUT n(H_n - H_{n-1}) is integer (1) ==>H_n can't be integer.

Uuh?? We don't need the preceeding part to "...hence $H_n-H_{n-1}$ not integer" to conclude this: it must be obvious that it is not an integer since for $1 ...and

thus your conclusion doesn't follow: for example, $\frac{1}{3}\,,\,\frac{2}{3}$ aren't integers, but $3\cdot\frac{1}{3}\,,\,3\cdot\frac{2}{3}$ are.

The proofs I know of this aren't hard but can be tricky. Hints for the most elementary one (that I know, of course):

If $H_n\in\mathbb{N}\,,\,\,then\,\,\,H_n\geq 2$ . Choose now $k\in\mathbb{N}\,\,\,s.t. \,\,\,1<2^k\leq n$ $\Longrightarrow l.c.m. (1,2,\ldots,n)=2^k\cdot 3^s\cdot5^r\cdot\ldots$ , and now divide and sum and stuff.

Tonio
• August 23rd 2010, 06:41 PM