Harmonic Number is not Integer

From ProofWiki
Jump to: navigation, search


Theorem

Let $H_n$ be the $n$th harmonic number.


Then $H_n$ is not an integer for $n \ge 2$.

That is, the only harmonic numbers that are integers are $H_0$ and $H_1$.


Proof

As $H_0 = 0$ and $H_1 = 1$, they are integers.

The claim is that $H_n$ is not an integer for all $n \ge 2$.


Aiming for a contradiction, suppose otherwise:

$(P): \quad \exists m \in \N: H_m \in \Z$

By the definition of the harmonic numbers:

$\displaystyle H_m = 1 + \frac 1 2 + \frac 1 3 + \ldots + \frac 1 m$


Let $2^t$ denote the highest power of two in the denominators of the summands.

Then:

\(\displaystyle H_m\) \(=\) \(\displaystyle 1 + \frac 1 2 + \frac 1 3 + \ldots + \frac 1 m\)
\((1):\quad\) \(\displaystyle \implies \ \ \) \(\displaystyle H_m - \frac 1 {2^t}\) \(=\) \(\displaystyle 1 + \frac 1 2 + \frac 1 3 + \ldots + \frac 1 {2^t - 1} + \frac 1 {2^t + 1} + \ldots + \frac 1 m\)
\(\displaystyle \implies \ \ \) \(\displaystyle 2^{t-1} H_m - \frac 1 2\) \(=\) \(\displaystyle 2^{t-1} + \frac {2^{t-1} } 2 + \frac {2^{t-1} } 3 + \frac {2^{t-1} } 4 + \frac {2^{t-1} } 5 + \frac {2^{t-1} } 6 + \ldots + \frac {2^{t-1} } m\) multiplying by $2^{t-1}$
\((2):\quad\) \(\displaystyle \) \(=\) \(\displaystyle 2^{t-1} + 2^{t-2} + \frac {2^{t-1} } 3 + 2^{t-3} + \frac {2^{t-1} } 5 + \frac {2^{t-2} } 3 + \ldots + \frac {2^{t-1} } m\) cancelling powers of $2$


Let $S$ be the set of denominators on the right hand side of $(2)$.

Then no element of $S$ can have $2$ as a factor, as follows.

Consider an arbitrary summand:

$\dfrac {2^{t-1}}{2^j \times k}$

for some $k \in \Z$, where $j \ge 0$ is the highest power of $2$ that divides the denominator.

For any $2$ to remain after simplification, we would need $j > t - 1$.

Were this to be so, then $2^j\times k$ would have $2^t$ as a factor, and some denominator would be a multiple of $2^t$.

By Greatest Power of Two not Divisor, the set of denominators of the right hand side of $(1)$:

$\left\{ {1, 2, 3, \ldots, 2^t - 1, 2^t + 1, \ldots, m}\right\}$

contains no multiple of $2^t$.

Therefore there can be no multiple of $2$ in the denominators of the right hand side of $(2)$.


Let:

$\ell = \lcm \left({S}\right)$

be the least common multiple of the elements of $S$.

Because all the elements of $S$ are odd, $\ell$ is likewise odd.



We have:

\(\displaystyle 2^{t-1} H_m - \frac 1 2\) \(=\) \(\displaystyle 2^{t-1} + 2^{t-2} + \frac {2^{t-1} } 3 + 2^{t-3} + \frac {2^{t-1} } 5 + \frac {2^{t-2} } 3 + \ldots + \frac {2^{t-1} } m\) from $(2)$
\(\displaystyle \implies \ \ \) \(\displaystyle \frac {2^t H_m - 1} 2\) \(=\) \(\displaystyle \frac{2^{t-1} \ell + 2^{t-2} \ell + 2^{t-1}\left({\ell/3}\right) + 2^{t-3} \ell + 2^{t-1}\left({\ell/5}\right) + \ldots + 2^{t-1} \left({\ell/m}\right)} \ell\) multiplying top and bottom by $\ell$
\(\displaystyle \implies \ \ \) \(\displaystyle \ell \left({2^t H_m - 1}\right)\) \(=\) \(\displaystyle 2 \left({2^{t-1} \ell + 2^{t-2} \ell + 2^{t-1}\left({\ell/3}\right) + 2^{t-3} \ell + 2^{t-1}\left({\ell/5}\right) + \ldots + 2^{t-1} \left({\ell/m}\right)}\right)\) multiplying both sides by $2 \ell$


But the left hand side of that last equation is odd, while its right hand side is even.

As this is a contradiction, it follows that our assumption $(P)$ that such an $m$ exists is false.

That is, there are no harmonic numbers apart from $0$ and $1$ which are integers.

$\blacksquare$


Sources