Kvant Math Problem 1032

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m51s
Source on kvant.digital

Problem

The numbers 2, 3, $\ldots$, $n+1$ are listed, along with all their possible products taken two at a time, three at a time, and so on up to the product of all $n$ of these numbers. Prove that the sum of the reciprocals of all the listed numbers equals $\dfrac n2$. $\Big($For example, when $n=3$: $$\dfrac12+\dfrac13+\dfrac14+\dfrac1{2\cdot3}+\dfrac1{2\cdot4}+\dfrac1{3\cdot4}+\dfrac1{2\cdot3\cdot4}=\dfrac32.\Big)$$

A. V. Andzhans

Exploration

Begin with small values of $n$ to detect a pattern. For $n=2$, the numbers are $2$ and $3$, and the products taken two at a time give $2\cdot 3=6$. The sum of reciprocals is

$$\frac{1}{2} + \frac{1}{3} + \frac{1}{6} = \frac{3}{6} + \frac{2}{6} + \frac{1}{6} = 1.$$

This equals $n/2 = 1$, confirming the claim for $n=2$. For $n=3$, as in the problem statement, the numbers are $2,3,4$; the products of two are $6,8,12$, and the product of three is $24$. Their reciprocals sum to

$$\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{12} + \frac{1}{24} = \frac{12+8+6+4+3+2+1}{24} = \frac{36}{24} = \frac{3}{2}.$$

This equals $n/2=3/2$. For $n=4$, the numbers are $2,3,4,5$, with products of two, three, and four numbers; computing the sum of reciprocals explicitly again yields $2$, which equals $n/2$. These calculations suggest a stable combinatorial pattern.

A key observation is that the sum of reciprocals over all products of subsets resembles evaluating a polynomial at $x=1$ for the generating function

$$f(x) = \prod_{k=2}^{n+1} \left(1 + \frac{x}{k}\right),$$

where the coefficient of $x^m$ corresponds to the sum of reciprocals of $m$-fold products. Evaluating $f(1)$ gives the total sum. The central difficulty is proving that this sum always equals $n/2$ without computing each term individually.

Problem Understanding

The problem asks to compute the sum of reciprocals of all nonempty products formed from the set ${2,3,\dots,n+1}$. It is a Type B problem because a specific equality is asserted, and we must prove it rigorously. The core difficulty is establishing a general combinatorial identity that holds for all $n$. The answer $n/2$ arises naturally from symmetry in the generating function and partial fraction decompositions; intuitively, each number contributes in a balanced way to the total sum.

Proof Architecture

Lemma 1. For the set ${2,3,\dots,n+1}$, the sum of reciprocals of all nonempty products is equal to evaluating

$$\prod_{k=2}^{n+1} \left(1 + \frac{1}{k}\right) - 1$$

and then adjusting for overlaps. This follows from the expansion of a product generating all subset reciprocals.

Lemma 2. The product $\prod_{k=2}^{n+1} \left(1 + \frac{1}{k}\right)$ simplifies as

$$\frac{3}{2} \cdot \frac{4}{3} \cdots \frac{n+2}{n+1} = \frac{n+2}{2}.$$

Lemma 3. Subtracting $1$ from this product accounts for removing the empty subset, yielding $\frac{n}{2}$. This step is critical and must be carefully justified.

The hardest step is Lemma 3, ensuring that the empty subset contribution corresponds exactly to subtracting $1$ and no further adjustment is needed.

Solution

Consider the set $S = {2,3,\dots,n+1}$. Form the product

$$f = \prod_{k=2}^{n+1} \left(1 + \frac{1}{k}\right).$$

Expanding this product gives exactly all possible sums of reciprocals of products of elements of $S$, including the empty product corresponding to $1$. Therefore, the sum of reciprocals of all nonempty products equals $f-1$.

Compute $f$ explicitly:

$$f = \prod_{k=2}^{n+1} \frac{k+1}{k} = \frac{3}{2} \cdot \frac{4}{3} \cdot \frac{5}{4} \cdots \frac{n+2}{n+1}.$$

Observe the telescoping: each numerator cancels the previous denominator, leaving

$$f = \frac{n+2}{2}.$$

Subtracting $1$ to remove the empty product yields

$$f - 1 = \frac{n+2}{2} - 1 = \frac{n}{2}.$$

Thus, the sum of the reciprocals of all nonempty products of numbers $2,3,\dots,n+1$ equals $n/2$.

This completes the proof. ∎

Verification of Key Steps

The telescoping product requires careful attention. Each term $\frac{k+1}{k}$ contributes a numerator $k+1$ and a denominator $k$, and the sequence cancels perfectly because $(3/2)(4/3)(5/4)\dots((n+2)/(n+1))$ leaves $n+2$ in the numerator and $2$ in the denominator. Testing small cases $n=2,3,4$ confirms the pattern holds. Removing the empty product by subtracting $1$ correctly counts only nonempty subsets; checking $n=2$ explicitly gives $(3/2)(4/3)-1=2/2=1$, consistent with the sum $\frac12+\frac13+\frac16=1$.

Alternative Approaches

A different approach is to apply the principle of inclusion-exclusion, summing reciprocals of single elements, then subtracting overlaps for pairs, adding triples, and so on. This combinatorial method ultimately leads to the same telescoping sum, but it requires more bookkeeping. The generating function approach is preferable because it provides a concise, systematic method that immediately captures the contribution of all subsets and naturally produces a telescoping product.