Sum over j of Function of Floor of mj over n

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f$ be a real function.

Then:

$\ds \sum_{0 \mathop \le j \mathop < n} \map f {\floor {\dfrac {m j} n} } = \sum_{0 \mathop \le r \mathop < m} \ceiling {\dfrac {r n} m} \paren {\map f {r - 1} - \map f r} + n \map f {m - 1}$


Corollary

$\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 r\) \(=\) \(\, \ds \floor {\dfrac {m j} n} \, \) \(\ds \)
\(\ds \leadsto \ \ \) \(\ds r\) \(\le\) \(\, \ds \dfrac {m j} n \, \) \(\, \ds < \, \) \(\ds r + 1\)
\(\ds \leadsto \ \ \) \(\ds \dfrac {r n} m\) \(\le\) \(\, \ds j \, \) \(\, \ds < \, \) \(\ds \dfrac {\paren {r + 1} n} m\)
\(\ds \leadsto \ \ \) \(\ds \ceiling {\dfrac {r n} m}\) \(\le\) \(\, \ds j \, \) \(\, \ds < \, \) \(\ds \ceiling {\dfrac {\paren {r + 1} n} m}\) as $j$ is an integer


Hence:

\(\ds \) \(\) \(\ds \sum_{0 \mathop \le j \mathop < n} \map f {\floor {\dfrac {m j} n} }\)
\(\ds \) \(=\) \(\ds \sum_{0 \mathop \le \ceiling {\frac {r n} m} \mathop < n} \map f r\)
\(\ds \) \(=\) \(\ds \sum_{0 \mathop \le r \mathop < m} \map f r \paren {\ceiling {\dfrac {\paren {r + 1} n} m} - \ceiling {\dfrac {r n} m} }\)
\(\ds \) \(=\) \(\ds \map f 0 \ceiling {\dfrac n m} + \map f 1 \paren {\ceiling {\dfrac {2 n} m} - \ceiling {\dfrac n m} } + \cdots + \map f {m - 1} \paren {\ceiling {\dfrac {m n} m} - \ceiling {\dfrac {\paren {m - 1} n} m} }\)
\(\ds \) \(=\) \(\ds \ceiling {\dfrac n m} \paren {\map f 0 + \map f 1} + \ceiling {\dfrac {2 n} m} \paren {\map f 0 + \map f 1} + \cdots + \ceiling {\dfrac {\paren {m - 1} n} m} \paren {\map f {m - 2} + \map f {m - 1} } + n \map f {m - 1}\)
\(\ds \) \(=\) \(\ds \sum_{0 \mathop \le r \mathop < m} \ceiling {\dfrac {r n} m} \paren {\map f {r - 1} + \map f r} + n \map f {m - 1}\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_over_j_of_Function_of_Floor_of_mj_over_n&oldid=565487"