-1

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.

Peter
  • 84,454
green_blue
  • 29
  • To be honest, the density argument is the most natural way to prove this, so I would recommend studying it and seeking out any definitions or results that it uses that you're unfamiliar with. The first argument is a way of adapting the density argument so that it doesn't use the notion of density—it's more concrete but also has more calculations. – Greg Martin Jan 14 '22 at 06:03
  • Thank you,could you please provide me with a note where i cam study it which also contains problems where i can apply. I am trying to learn this for olympiad. – green_blue Jan 14 '22 at 06:12

1 Answers1

1

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$.

J.G.
  • 115,835
  • https://youtu.be/_63umB2kE9k here is the video,actually the solution starts from 20:17 and thanks a lot. Could you please shed some light on the constant terms they wrote along with $\frac{k}{d_i}$ which i mentioned in the post too. – green_blue Jan 14 '22 at 09:48
  • Also i would be really greatful if you could also demonstrate the density argument simply so that i can learn the gist of it and try to apply in future problems. Or a note for this in olympiad level will be really very helpful. – green_blue Jan 14 '22 at 09:51
  • @green_blue The $\pm\operatorname{constant}$ step is just my within-$1$ point, without making explicit that the constant is $1$ (the argument doesn't actually need to work out what it is). Since density is the $k\to\infty$ limit of the proportion of small numbers in progression $i$, the density argument is to prove this limit is $1/d_i$ by the squeeze theorem, since the proportion is between $1/d_i\pm C/k$ (where, as I said, $C=1$ but we don't need to know that). – J.G. Jan 14 '22 at 09:55