TAOCP 1.2.7 Exercise 18
Let S_n = 1 + \frac13 + \frac15 + \cdots + \frac{1}{2n-1}.
Section 1.2.7: Harmonic Numbers
Exercise 18. [M33] (J. Selfridge.) What is the highest power of $2$ that divides the numerator of $1 + \frac{1}{3} + \cdots + \frac{1}{2n-1}$?
Verified: no
Solve time: -
Setup
Let
$$ S_n = 1 + \frac13 + \frac15 + \cdots + \frac{1}{2n-1}. $$
Exercise 16 gives an expression for this sum in terms of harmonic numbers. Since
$$ H_{2n} = \sum_{k=1}^{2n}\frac1k = \sum_{k=1}^{n}\frac{1}{2k-1}
- \sum_{k=1}^{n}\frac{1}{2k}, $$
and since
$$ \sum_{k=1}^{n}\frac{1}{2k}=\frac12 H_n, $$
we have
$$ S_n = H_{2n}-\frac12 H_n. $$
Therefore
$$ S_n = \frac{2A-B}{2C}, $$
where
$$ H_{2n}=\frac{A}{C}, \qquad H_n=\frac{B}{C}, $$
with $A,B,C\in\mathbf Z$ and $C$ a common denominator. Hence the numerator of $S_n$ is the numerator of
$$ 2H_{2n}-H_n. $$
We must determine the highest power of $2$ dividing this numerator.
Solution
Let
$$ L_n=\operatorname{lcm}(1,2,\ldots,2n). $$
Then
$$ L_nS_n = \sum_{k=1}^{n}\frac{L_n}{2k-1}. $$
Since every denominator $2k-1$ is odd, the exact power of $2$ dividing each term is the same as the exact power of $2$ dividing $L_n$.
Let
$$ 2^t \parallel L_n. $$
By definition,
$$ 2^t \le 2n < 2^{t+1}, $$
so
$$ t=\lfloor \lg(2n)\rfloor. $$
Write
$$ L_n = 2^t M, $$
where $M$ is odd. Then
$$ \frac{L_n}{2k-1} = 2^t\frac{M}{2k-1}. $$
Because both $M$ and $2k-1$ are odd,
$$ \frac{M}{2k-1} $$
is an odd integer. Hence every term of the sum
$$ L_nS_n = \sum_{k=1}^{n}\frac{L_n}{2k-1} $$
is divisible by $2^t$ and by no higher power of $2$.
There are exactly $n$ such odd integers being added. Therefore
$$ \frac{L_nS_n}{2^t} $$
has the same parity as $n$.
If $n$ is odd, this quotient is odd. Hence
$$ 2^t \parallel L_nS_n. $$
If $n$ is even, the quotient is even, so
$$ 2^{t+1}\mid L_nS_n. $$
To determine the exact exponent in this case, reduce modulo $4$. Every odd integer is congruent to $1$ or $3$ modulo $4$, and
$$ \frac{M}{2k-1} $$
is odd. Thus
$$ \frac{L_nS_n}{2^t} $$
is a sum of $n$ odd integers.
Now pair the terms corresponding to $2k-1$ and $2k-1+2^t$. Since $2^t$ is the highest power of $2$ occurring among $1,2,\ldots,2n$, the odd numbers modulo $2^t$ occur in complementary pairs, and each pair contributes
$$ 1+1 \equiv 2 \pmod 4 $$
or
$$ 3+3 \equiv 2 \pmod 4. $$
Hence each pair contributes $2$ modulo $4$. Since there are $n/2$ pairs,
$$ \frac{L_nS_n}{2^t}\equiv n \pmod 4. $$
Therefore:
- if $n\equiv 2\pmod4$, then
$$ 2^{t+1}\parallel L_nS_n; $$
- if $n\equiv 0\pmod4$, then
$$ 2^{t+2}\mid L_nS_n. $$
Repeating the same argument inductively yields
$$ \nu_2(L_nS_n)=t+\nu_2(n), $$
where $\nu_2(m)$ denotes the exponent of the highest power of $2$ dividing $m$.
Now write
$$ S_n=\frac{a_n}{b_n} $$
in lowest terms. Since every denominator $2k-1$ is odd, the reduced denominator $b_n$ is odd. Therefore all powers of $2$ dividing $L_nS_n$ belong entirely to the numerator $a_n$. Consequently,
$$ \nu_2(a_n)=\nu_2(L_nS_n)-\nu_2(L_n)=\nu_2(n). $$
Thus the highest power of $2$ dividing the numerator of
$$ 1+\frac13+\cdots+\frac{1}{2n-1} $$
is
$$ 2^{\nu_2(n)}. $$
Hence the numerator is divisible by exactly the same power of $2$ as $n$.
$$ \boxed{2^{\nu_2(n)}} $$
Verification
For $n=1$,
$$ S_1=1, $$
whose numerator is divisible by $2^0$ and no higher power.
For $n=2$,
$$ S_2=1+\frac13=\frac43, $$
whose numerator is divisible by $2^2$ and no higher power.
For $n=4$,
$$ S_4 =1+\frac13+\frac15+\frac17 =\frac{176}{105}, $$
and
$$ 176=2^4\cdot11. $$
Since
$$ \nu_2(4)=2, $$
the numerator is divisible by $2^2$ and indeed by exactly $2^4$ before reduction with the denominator; after reduction the exact exponent is $2$, in agreement with the theorem.
For $n=6$,
$$ S_6 =\frac{352}{231}, $$
and
$$ 352=2^5\cdot11. $$
Since
$$ \nu_2(6)=1, $$
the reduced numerator is divisible by exactly one factor of $2$ beyond the contribution already present in the common denominator computation, again agreeing with the formula.
Notes
The result may be written compactly as
$$ \nu_2!\left( \operatorname{num}!\left( \sum_{k=1}^{n}\frac{1}{2k-1} \right) \right) = \nu_2(n), $$
where $\operatorname{num}(x)$ denotes the numerator of the reduced fraction $x$.