Sum of the reciprocals of the differences is $1$

39 Views Asked by At

We have distinct arithmetic progressions with common differences $d_1, d_2, \cdots,d_n$. If every natural number belongs to exactly one arithmetic progression, prove that $\frac{1}{d_1}+\frac{1}{d_2}+\cdots+\frac{1}{d_n}=1$.

I saw two proofs of this but none of them explained it clearly. The first one was to choose a large number $k$ and deduced that the numbers not greater than $k$ appearing in $i$th sequence is $\frac{k}{d_i}+/-$ a constant. I didn't understand what they did here. Finally they added all such numbers and got $\frac{k}{d_1}+\frac{k}{d_2}+\cdots+\frac{k}{d_n}+$ a constant$=k$ and by choosing $k$ large enough they said $\frac{1}{d_1}+\frac{1}{d_2}+\cdots+\frac{1}{d_n}=1$ which i didn't get how.

Next they used a density argument saying that the density of first A.P is $\frac{1}{d_1}$ and such which also i didn't understand. It would be very helpful if these solutions are explained in simple language.

1

There are 1 best solutions below

3
On

You don't quote or link to the arguments you've seen, so I'll try to spell out what they likely meant.

Of the positive integers from $1$ to $k$ inclusive (hereafter "small" numbers), the number in the progression of common difference $d_i$ can be bounded as follows. Write $k=qd_i+r$ for integers $q,\,r$, specified uniquely by $0\le r<d_i$. If some integer from $1$ to $r$ inclusive is in the progression, $q+1$ small numbers are in the progression; if not, only $q$ are. (It can't be even fewer, since this would require the least small number in the progression to exceed $d+r$, even though we could subtract $d$ repeatedly to obtain a counterexample.) Since$$qd_i\le k<(q+1)d_i,$$$q>k/d_i-1$ and $q+1\le k/d_i+1$, so $k/d_i$ is within $1$ of the number of small numbers in the progression. Therefore, $|\sum_i k/d_i-k|\le n$, i.e. $|\sum_i 1/d_i-1|\le n/k$. This is true for all $k\in\Bbb N$, so $\sum_i 1/d_i=1$.