2
$\begingroup$

Suppose that we have a collection $S_1 = \{a_1 + kr_1\}_{k=0}^{\infty}$, $\cdots$, $S_n = \{a_n + kr_n\}_{k=0}^{\infty}$ of disjoint arithmetic sequences where $a_i$, $r_i$ are nonnegative integers for all $1\le i \le n$. Furthermore, assume that these sequences cover $\mathbb{Z}_{\ge 0}$: $$\mathbb{N} \cup \{0\} = S_1 \cup S_2 \cup \cdots \cup S_n$$

Then, one has the formal equality of power series $$\frac{1}{1-x} = \sum_{k=0}^{\infty} x^k = \sum_{i=1}^{n} \sum_{k=0}^{\infty} x^{a_i + k r_i} = \sum_{i=1}^{n} \frac{x^{a_i}}{1-x^{r_i}} $$ Multiplying both sides by $1-x$ and taking $x\to 1^{-}$ proves that $$\frac{1}{r_1} + \frac{1}{r_2} + \cdots + \frac{1}{r_n} = 1 \tag{1}$$ Differentiating both sides and taking $x\to 1^{-}$ again shows $$\frac{a_1}{r_1} + \frac{a_2}{r_2} + \cdots + \frac{a_n}{r_n} = \frac{n-1}{2} \tag{2}$$

The first of these identities has a direct combinatorial/number theoretic proof. Let $N = r_1 r_2 \cdots r_n$. Then $S_i$ accounts for precisely $N/r_i$ of the residue classes modulo $N$. Since there are $N$ residue classes, the equation $$\frac{N}{r_1} + \cdots + \frac{N}{r_n} = N$$ yields identity $(1)$. Is there a similar direct counting argument for identity $(2)$?

$\endgroup$
2
$\begingroup$

The equality $2$ can be determined using the observation that the sum of all elements belonging to each set $S_i$ is the sum of all residues so: $$ \overbrace{\frac{N}{r_1}a_1+r_1.\frac{N}{2r_1}(\frac{N}{r_1}-1)}^{\text{The sum of residus }\in S_1}+\cdots\cdots+\overbrace{\frac{N}{r_n}a_n+r_n.\frac{N}{2r_n}(\frac{N}{r_1}-1)}^{\text{The sum of residus }\in S_n}=\overbrace{\frac{N(N-1)}{2}}^{\text{The sum of all residus }}$$

with some simplification you get $(2)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.