TAOCP 1.2.4 Exercise 45
Let S=\sum_{0\le j<n}f\!
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 45. ▶ [M28] The result of exercise 37 is somewhat surprising, since it implies that
$$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \sum_{0 \le k < m} \left\lfloor \frac{nk+x}{m} \right\rfloor $$
when $m$ and $n$ are positive integers and $x$ is arbitrary. This “reciprocity relationship” is one of many similar formulas (see Section 3.3.3). Show that in general we have
$$ \sum_{0 \le j < n} f\left(\left\lfloor \frac{mj}{n} \right\rfloor\right) = \sum_{0 \le r < m} \left\lceil \frac{rn}{m} \right\rceil \bigl(f(r-1)-f(r)\bigr) + n f(m-1) $$
for any function $f$ and all integers $m,n>0$. In particular, prove that
$$ \sum_{0 \le j < n} \binom{\lfloor mj/n \rfloor + 1}{k} + \sum_{0 \le j < m} \left\lceil \frac{jn}{m} \right\rceil \binom{j}{k-1} = n\binom{m}{k}. $$
[Hint: Consider the change of variable $r=\lfloor mj/n \rfloor$. Binomial coefficients $\binom{m}{k}$ are discussed in Section 1.2.6.]
Verified: yes
Solve time: 51s
Setup
Let
$$ S=\sum_{0\le j<n}f!\left(\left\lfloor \frac{mj}{n}\right\rfloor\right), \qquad m,n>0. $$
We are to prove the identity
$$ S= \sum_{0\le r<m} \left\lceil \frac{rn}{m}\right\rceil \bigl(f(r-1)-f(r)\bigr) +n f(m-1), \tag{1} $$
valid for an arbitrary function $f$. Then we shall deduce the special case
$$ \sum_{0\le j<n} \binom{\lfloor mj/n\rfloor+1}{k} + \sum_{0\le j<m} \left\lceil \frac{jn}{m}\right\rceil \binom{j}{k-1} = n\binom{m}{k}. \tag{2} $$
The hint suggests the change of variable
$$ r=\left\lfloor \frac{mj}{n}\right\rfloor . $$
Solution
Fix an integer $r$ with $0\le r<m$. 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}. $$
Since $j$ is an integer, the number of such $j$ equals
$$ \left\lceil \frac{(r+1)n}{m}\right\rceil - \left\lceil \frac{rn}{m}\right\rceil. $$
Therefore
$$ S = \sum_{0\le r<m} \left( \left\lceil \frac{(r+1)n}{m}\right\rceil - \left\lceil \frac{rn}{m}\right\rceil \right) f(r). \tag{3} $$
We separate the two sums:
$$ S = \sum_{0\le r<m} \left\lceil \frac{(r+1)n}{m}\right\rceil f(r) - \sum_{0\le r<m} \left\lceil \frac{rn}{m}\right\rceil f(r). \tag{4} $$
In the first sum, replace $r+1$ by $s$:
$$ \sum_{0\le r<m} \left\lceil \frac{(r+1)n}{m}\right\rceil f(r) = \sum_{1\le s\le m} \left\lceil \frac{sn}{m}\right\rceil f(s-1). $$
Since
$$ \left\lceil \frac{mn}{m}\right\rceil=n, $$
equation (4) becomes
$$ S = \sum_{1\le s<m} \left\lceil \frac{sn}{m}\right\rceil f(s-1) +n f(m-1) - \sum_{0\le r<m} \left\lceil \frac{rn}{m}\right\rceil f(r). \tag{5} $$
The term with $r=0$ in the second sum vanishes because
$$ \left\lceil \frac{0\cdot n}{m}\right\rceil=0. $$
Relabel $s$ as $r$ in the first sum and combine terms:
$$ S = \sum_{0\le r<m} \left\lceil \frac{rn}{m}\right\rceil \bigl(f(r-1)-f(r)\bigr) +n f(m-1). $$
This proves (1).
To obtain the binomial identity, choose
$$ f(r)=\binom{r+1}{k}. $$
Then, by the elementary identity
$$ \binom{r+1}{k}-\binom{r}{k} = \binom{r}{k-1}, $$
we have
$$ f(r-1)-f(r) = \binom{r}{k}-\binom{r+1}{k} = -\binom{r}{k-1}. $$
Substituting into (1) gives
$$ \sum_{0\le j<n} \binom{\lfloor mj/n\rfloor+1}{k} = - \sum_{0\le r<m} \left\lceil \frac{rn}{m}\right\rceil \binom{r}{k-1} + n\binom{m}{k}. $$
Transposing the second term to the left-hand side yields
$$ \sum_{0\le j<n} \binom{\lfloor mj/n\rfloor+1}{k} + \sum_{0\le j<m} \left\lceil \frac{jn}{m}\right\rceil \binom{j}{k-1} = n\binom{m}{k}. $$
Hence (2) is proved.
This completes the proof.
∎
Verification
We verify the counting formula used in (3). For fixed $r$,
$$ r\le \frac{mj}{n}<r+1 $$
implies
$$ \frac{rn}{m}\le j<\frac{(r+1)n}{m}. $$
The integers in an interval $[a,b)$ are precisely
$$ \lceil a\rceil,, \lceil a\rceil+1,, \ldots,, \lceil b\rceil-1, $$
hence their number is
$$ \lceil b\rceil-\lceil a\rceil. $$
Applying this with
$$ a=\frac{rn}{m}, \qquad b=\frac{(r+1)n}{m}, $$
gives the coefficient of $f(r)$ in (3).
For the special case $f(r)=\binom{r+1}{k}$,
$$ f(m-1)=\binom{m}{k}, $$
and
$$ f(r-1)-f(r) = \binom{r}{k}-\binom{r+1}{k} = -\binom{r}{k-1}, $$
by Pascal’s identity. The resulting formula is exactly (2).
Notes
Identity (1) is a discrete summation-by-parts formula obtained by grouping together all indices $j$ for which
$$ \left\lfloor \frac{mj}{n}\right\rfloor=r. $$
The reciprocity relation mentioned in the exercise is recovered by selecting suitable functions $f$, as in exercise 37.