TAOCP 1.2.4 Exercise 46
Let S(\alpha)=\sum_{0\le j<\alpha n} f\!
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 46. [M29] (General reciprocity law.) Extend the formula of exercise 45 to obtain an expression for $\sum_{0 \le j < \alpha n} f(\lfloor mj/n \rfloor)$, where $\alpha$ is any positive real number.
Verified: yes
Solve time: 1m10s
Setup
Let
$$ S(\alpha)=\sum_{0\le j<\alpha n} f!\left(\left\lfloor \frac{mj}{n}\right\rfloor\right), $$
where $m,n>0$ are integers and $\alpha>0$ is real.
Exercise 45 corresponds to the special case $\alpha=1$. We seek a formula valid for arbitrary $\alpha$.
Put
$$ t=\lfloor \alpha n\rfloor . $$
Then
$$ S(\alpha)=\sum_{j=0}^{t-1} f!\left(\left\lfloor \frac{mj}{n}\right\rfloor\right). $$
For each integer $r\ge0$, define
$$ N_r=#\Bigl{j:0\le j<t,, \Bigl\lfloor \frac{mj}{n}\Bigr\rfloor=r\Bigr}. $$
Then
$$ S(\alpha)=\sum_{r\ge0}N_r,f(r). $$
The problem is therefore reduced to determining $N_r$.
Solution
The condition
$$ \left\lfloor \frac{mj}{n}\right\rfloor=r $$
is equivalent to
$$ r\le \frac{mj}{n}<r+1, $$
hence to
$$ \frac{rn}{m}\le j<\frac{(r+1)n}{m}. $$
Together with $0\le j<t$, this yields
$$ N_r= #\Bigl{j: \Bigl\lceil\frac{rn}{m}\Bigr\rceil \le j < \min!\Bigl(t,\Bigl\lceil\frac{(r+1)n}{m}\Bigr\rceil\Bigr) \Bigr}. $$
Therefore
$$ N_r= \max!\left( 0,, \min!\Bigl(t,\Bigl\lceil\frac{(r+1)n}{m}\Bigr\rceil\Bigr) - \Bigl\lceil\frac{rn}{m}\Bigr\rceil \right). \tag{1} $$
Let
$$ R=\left\lfloor\frac{m(t-1)}{n}\right\rfloor . $$
Then $N_r=0$ for $r>R$, and (1) becomes
$$ N_r= \min!\Bigl(t,\Bigl\lceil\frac{(r+1)n}{m}\Bigr\rceil\Bigr) - \Bigl\lceil\frac{rn}{m}\Bigr\rceil , \qquad 0\le r\le R. $$
Hence
$$ S(\alpha) = \sum_{r=0}^{R} \left( \min!\Bigl(t,\Bigl\lceil\frac{(r+1)n}{m}\Bigr\rceil\Bigr) - \Bigl\lceil\frac{rn}{m}\Bigr\rceil \right) f(r). \tag{2} $$
Apply summation by parts. Let
$$ A_r= \min!\Bigl(t,\Bigl\lceil\frac{rn}{m}\Bigr\rceil\Bigr). $$
Then (2) is
$$ S(\alpha) = \sum_{r=0}^{R}(A_{r+1}-A_r)f(r). $$
Since $A_0=0$,
$$ \sum_{r=0}^{R}(A_{r+1}-A_r)f(r) = \sum_{r=1}^{R}A_r\bigl(f(r-1)-f(r)\bigr) +A_{R+1}f(R). $$
Because
$$ A_{R+1} = \min!\Bigl(t,\Bigl\lceil\frac{(R+1)n}{m}\Bigr\rceil\Bigr) =t, $$
we obtain
$$ \boxed{ \sum_{0\le j<\alpha n} f!\left(\left\lfloor\frac{mj}{n}\right\rfloor\right) = \sum_{r=1}^{R} \min!\Bigl(\lfloor\alpha n\rfloor, \Bigl\lceil\frac{rn}{m}\Bigr\rceil\Bigr) \bigl(f(r-1)-f(r)\bigr) + \lfloor\alpha n\rfloor,f(R) } $$
where
$$ R= \left\lfloor \frac{m(\lfloor\alpha n\rfloor-1)}{n} \right\rfloor . $$
This is the desired extension of the reciprocity formula.
When $\alpha=1$, we have $t=n$ and $R=m-1$. Since
$$ \Bigl\lceil\frac{rn}{m}\Bigr\rceil\le n \qquad (0\le r\le m), $$
the minimum sign disappears, giving
$$ \sum_{0\le j<n} f!\left(\left\lfloor\frac{mj}{n}\right\rfloor\right) = \sum_{0\le r<m} \Bigl\lceil\frac{rn}{m}\Bigr\rceil \bigl(f(r-1)-f(r)\bigr) + n,f(m-1), $$
which is exactly the formula of Exercise 45.
Verification
For each $r$, the integers counted by $N_r$ are precisely those in the interval
$$ \left[ \Bigl\lceil\frac{rn}{m}\Bigr\rceil,, \Bigl\lceil\frac{(r+1)n}{m}\Bigr\rceil \right), $$
truncated at $t=\lfloor\alpha n\rfloor$. Formula (1) therefore counts them correctly.
The coefficients in (2) satisfy
$$ \sum_{r=0}^{R} \left( \min!\Bigl(t,\Bigl\lceil\frac{(r+1)n}{m}\Bigr\rceil\Bigr) - \Bigl\lceil\frac{rn}{m}\Bigr\rceil \right) =t, $$
so the total number of terms counted is exactly $t$, matching the left-hand side.
Substituting $t=n$ recovers Exercise 45, confirming that the general formula specializes correctly.
Notes
An equivalent form is obtained by writing
$$ t=\lfloor\alpha n\rfloor,\qquad M=\left\lfloor\frac{mt}{n}\right\rfloor , $$
and separating the values of $r$ for which
$\lceil rn/m\rceil<t$ from those for which
$\lceil rn/m\rceil\ge t$. The formula above is the most direct analogue of the reciprocity law of Exercise 45. ∎