Sum over j of Function of Floor of mj over n/Corollary

Corollary to Sum over $j$ of $\map f {\floor {\frac {m j} n} }$

$\ds \sum_{0 \mathop \le j \mathop < n} \binom {\floor {m j / n} + 1} k + \sum_{0 \mathop \le j \mathop < m} \ceiling {\dfrac {j n} m} \binom j {k - 1} = n \binom m k$

Proof

\(\ds \sum_{0 \mathop \le j \mathop < n} \binom {\floor {m j / n} + 1} k\)

\(=\)

\(\ds \sum_{0 \mathop \le r \mathop < m} \ceiling {\dfrac {r n} m} \paren {\binom r k - \binom {r + 1} k} + n \binom m k\)

Sum over $j$ of $\map f {\floor {\dfrac {m j} n} }$

\(\ds \)

\(=\)

\(\ds \sum_{0 \mathop \le j \mathop < m} \ceiling {\dfrac {j n} m} \paren {-\binom j {k - 1} } + n \binom m k\)

Pascal's Rule and renaming

Hence:

\(\ds \sum_{0 \mathop \le j \mathop < n} \binom {\floor {m j / n} + 1} k + \sum_{0 \mathop \le j \mathop < m} \ceiling {\dfrac {j n} m} \binom j {k - 1}\)

\(=\)

\(\ds n \binom m k\)

$\blacksquare$

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $45$