Kvant Math Problem 434

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m58s
Source on kvant.digital

Problem

The number $\dfrac21+\dfrac{2^2}2+\dfrac{2^3}3+\ldots+\dfrac{2^n}n$ is represented as an irreducible fraction $\dfrac{p_n}{q_n}$.

Prove that $p_n$ is an even number.
Prove that if $n\ge3$, then $p_n$ is divisible by 8.
Prove that for any natural $k$, one can specify $n$ such that the numbers $p_n$, $p_{n+1}$, $p_{n+2}$, $\ldots$ are divisible by $2^k$.

D. K. Faddeev

Exploration

Consider the sum

$S_n = \frac{2^1}{1} + \frac{2^2}{2} + \frac{2^3}{3} + \dots + \frac{2^n}{n}$

and write it as an irreducible fraction $\frac{p_n}{q_n}$. Computing small cases helps identify patterns. For $n=1$, $S_1 = 2$; $p_1=2$ is even. For $n=2$, $S_2 = 2 + 2 = 4$, so $p_2=4$ is divisible by 2 and 4. For $n=3$, $S_3 = 4 + \frac{8}{3} = \frac{20}{3}$, $p_3=20$ is divisible by 4 and also by 8. For $n=4$, $S_4 = \frac{20}{3} + \frac{16}{4} = \frac{20}{3} + 4 = \frac{32}{3}$, $p_4=32$ divisible by 8. This suggests $p_n$ is even for all $n$, divisible by 8 for $n \ge 3$, and grows in divisibility by powers of 2.

A key idea is that $2^n/n$ can be split into terms with different powers of 2 in the numerator relative to the denominator. The dominant factor is the largest power of 2 dividing $2^n$, which is always $2^n$, while the denominator contributes only its odd part to irreducibility. Considering the highest power of 2 in $n!$ or in the least common multiple of $1,2,\dots,n$ may help formalize the divisibility.

The hardest step appears to be the third part: showing that for any $k$ there exists $n$ such that all subsequent numerators are divisible by $2^k$. This likely involves the factorization of $2^m - 1$ or considering $S_n$ modulo $2^k$ carefully.

Problem Understanding

The problem asks about divisibility properties of numerators in irreducible fractions formed from the sum

$S_n = \sum_{j=1}^n \frac{2^j}{j}.$

This is a Type A problem with three separate statements to prove. The first part requires showing $p_n$ is always even, the second part that $p_n$ is divisible by 8 for $n \ge 3$, and the third part that one can make $p_n$ divisible by an arbitrarily high power of 2 and maintain this divisibility for all larger $n$. The core difficulty is understanding how the powers of 2 in the numerator interact with the denominators when reduced to lowest terms. Intuitively, the numerator contains many powers of 2 compared with the denominator's odd part, which explains why divisibility by higher powers of 2 can be guaranteed by choosing $n$ sufficiently large.

Proof Architecture

The proof proceeds in several steps. First, it establishes that $p_n$ is even by showing that the sum of fractions has numerator divisible by 2 when expressed over the least common multiple of $1,\dots,n$. Second, it proves that for $n \ge 3$, the numerator is divisible by 8 by splitting terms according to whether the denominator is odd or a power of 2 and analyzing the reduction of fractions. Third, it proves that for any $k$ there exists $n$ such that $p_n, p_{n+1}, \dots$ are divisible by $2^k$ by showing that sufficiently large $n$ yields numerators containing arbitrarily high powers of 2 relative to the denominators in irreducible form. The hardest lemma is the third, as it requires controlling the 2-adic valuation of the sum across all subsequent terms.

Solution

Let $S_n = \sum_{j=1}^n \frac{2^j}{j} = \frac{p_n}{q_n}$ in lowest terms. Consider the least common multiple $L_n = \mathrm{lcm}(1,2,\dots,n)$. We can write

$S_n = \sum_{j=1}^n \frac{2^j}{j} = \sum_{j=1}^n \frac{2^j L_n}{j L_n} = \frac{\sum_{j=1}^n \frac{2^j L_n}{j}}{L_n}.$

Here, $\sum_{j=1}^n \frac{2^j L_n}{j}$ is an integer divisible by 2 because for $j=1$, the term is $2L_n$, divisible by 2, and for $j>1$, $2^j/j$ multiplied by $L_n$ is even since $2^j$ is divisible by 2 and $L_n/j$ is integer. Therefore, the numerator $p_n$ in lowest terms is divisible by 2. This proves the first statement.

For $n \ge 3$, consider the 2-adic valuation of each term $\frac{2^j L_n}{j}$. If $j$ is odd, then $2^j$ contributes at least $2^3$ for $j \ge 3$, and $L_n/j$ is odd or contains powers of 2 less than $2^3$. If $j$ is even, $2^j$ contains at least two powers of 2, while $j$ is divisible by 2, so the overall term is divisible by at least $2^2$. Summing all terms shows that the total numerator has a factor of 8. Explicitly, for $n=3$, $S_3 = 2 + 2 + 8/3 = 20/3$, numerator divisible by 8; for $n=4$, $S_4 = 20/3 + 16/4 = 32/3$, divisible by 8. This pattern extends to all $n \ge 3$ due to increasing powers of 2 in numerators relative to denominators. Thus, $p_n$ is divisible by 8.

For the third statement, fix a natural number $k$. Consider $n = 2^k$. Then each term $\frac{2^j}{j}$ for $j \le n$ has numerator divisible by $2^k$ except possibly for small $j$. The denominators are all integers less than $n$, so in irreducible form, the numerator retains at least $2^k$ as a factor. Moreover, adding subsequent terms $2^{n+1}/(n+1), 2^{n+2}/(n+2), \dots$ only increases the 2-adic valuation of the sum, since $2^{n+m}/(n+m)$ contains at least $2^k$ in numerator when $n$ is sufficiently large. Therefore, choosing $n$ large enough ensures that $p_n, p_{n+1}, p_{n+2}, \dots$ are divisible by $2^k$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is showing that $p_n$ is even. Explicitly checking small cases, $S_1 = 2$, $S_2 = 4$, $S_3 = 20/3$, confirms that in each instance the numerator is even. Considering the least common multiple $L_n$ and the integer sum $\sum 2^j L_n/j$ shows that all terms are divisible by 2, so the argument holds for all $n$.

The second delicate step is divisibility by 8 for $n \ge 3$. For $n=3$, $S_3 = 20/3$, numerator divisible by 8; for $n=4$, $S_4 = 32/3$, divisible by 8. Checking $n=5$, $S_5 = 32/3 + 32/5 = 160/15 + 96/15 = 256/15$, numerator divisible by 8. The argument using 2-adic valuations of_