TAOCP 1.2.7 Exercise 19
Let H_n=\sum_{k=1}^{n}\frac{1}{k}, \qquad H_0=0.
Section 1.2.7: Harmonic Numbers
Exercise 19. [M30] List all nonnegative integers $n$ for which $H_n$ is an integer.
Verified: no
Solve time: -
Setup
Let
$$ H_n=\sum_{k=1}^{n}\frac{1}{k}, \qquad H_0=0. $$
We seek all nonnegative integers $n$ for which $H_n$ is an integer.
The problem therefore asks for all $n \ge 0$ such that
$$ \sum_{k=1}^{n}\frac{1}{k}\in \mathbf Z. $$
We will prove that the only such values are
$$ n=0 \quad \text{and} \quad n=1. $$
Solution
The values
$$ H_0=0, \qquad H_1=1 $$
are integers. It remains to prove that $H_n$ is not an integer for every $n\ge 2$.
Fix $n\ge 2$. Let $2^m$ be the unique power of $2$ satisfying
$$ 2^m\le n<2^{m+1}. $$
Among the integers $1,2,\ldots,n$, exactly one is divisible by $2^m$, namely $2^m$ itself. Every other denominator has smaller $2$-adic divisibility.
Write each denominator in the form
$$ k=2^{\nu(k)}u_k, $$
where $u_k$ is odd and $\nu(k)\ge 0$. Since $2^m$ is the largest power of $2$ not exceeding $n$, we have $\nu(k)\le m$ for all $k\le n$, and equality holds only for $k=2^m$.
Let
$$ L=\operatorname{lcm}(1,2,\ldots,n). $$
Then
$$ H_n = \frac{L}{1L} + \frac{L}{2L} + \cdots + \frac{L}{nL} = \frac{\displaystyle \sum_{k=1}^{n}L/k}{L}. $$
The integer $L$ is divisible by $2^m$, but not by $2^{m+1}$, because no denominator in ${1,\ldots,n}$ contains a higher power of $2$ than $2^m$. Hence
$$ \nu(L)=m. $$
Consider the numerator
$$ N=\sum_{k=1}^{n}\frac{L}{k}. $$
When $k=2^m$,
$$ \frac{L}{2^m} $$
is odd, since $\nu(L)=m$.
When $k\ne 2^m$, we have $\nu(k)\le m-1$, therefore
$$ \nu!\left(\frac{L}{k}\right) = m-\nu(k) \ge 1, $$
so every term $L/k$ is even.
Thus $N$ is the sum of one odd integer and several even integers, hence $N$ is odd.
Suppose $H_n$ were an integer. Since
$$ H_n=\frac{N}{L}, $$
the denominator $L$ would divide $N$. But $L$ is even, because $m\ge 1$ for $n\ge 2$, while $N$ is odd. An even integer cannot divide an odd integer. This contradiction proves that $H_n$ is not an integer for any $n\ge 2$.
Therefore the complete set of nonnegative integers $n$ for which $H_n$ is an integer is
$$ \boxed{{0,1}}. $$
Verification
For $n=0$ and $n=1$,
$$ H_0=0, \qquad H_1=1, $$
both integers.
For $n=2$,
$$ H_2=1+\frac12=\frac32, $$
not an integer.
For $n=3$,
$$ H_3=1+\frac12+\frac13=\frac{11}{6}, $$
not an integer.
The argument above proves uniformly that every $n\ge 2$ fails.
Notes
The proof exploits the unique denominator containing the highest power of $2$. Exercise 18 studies the same phenomenon for the odd harmonic sum
$$ 1+\frac13+\cdots+\frac{1}{2n-1}, $$
by determining the exact power of $2$ dividing its numerator.