Sum over k of Floor of Log base b of k

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{> 0}$ be a strictly positive integer.

Let $b \in \Z$ such that $b \ge 2$.

Then:

$\ds \sum_{k \mathop = 1}^n \floor {\log_b k} = \paren {n + 1} \floor {\log_b n} - \dfrac {b^{\floor {\log_b n} + 1} - b} {b - 1}$


Proof

From Sum of Sequence as Summation of Difference of Adjacent Terms:

$(1): \quad \ds \sum_{k \mathop = 1}^n \floor {\log_b k} = n \floor {\log_b n} - \sum_{k \mathop = 1}^{n - 1} k \paren {\floor {\map {\log_b} {k + 1} } - \floor {\log_b k} }$

Let $S$ be defined as:

$\ds S := \sum_{k \mathop = 1}^{n - 1} k \paren {\floor {\map {\log_b} {k + 1} } - \floor {\log_b k} }$


As $b \ge 2$, we have that:

$\map {\log_b} {k + 1} - \log_b k < 1$

As $b$ is an integer:

$\lfloor {\map {\log_b} {k + 1} } - \floor {\log_b k} = 1$

if and only if $k + 1$ is a power of $b$.


So:

\(\ds S\) \(=\) \(\ds \sum_{k \mathop = 1}^{n - 1} k \sqbrk {k + 1 \text{ is a power of } b}\) where $\sqbrk {\, \cdot \,}$ is Iverson's convention
\(\ds \) \(=\) \(\ds \sum_{1 \mathop \le t \mathop \le \log_b n} \paren {b^t - 1}\)
\(\ds \) \(=\) \(\ds \sum_{t \mathop = 1}^{\floor {\log_b n} } \paren {b^t - 1}\)
\(\ds \) \(=\) \(\ds \sum_{t \mathop = 1}^{\floor {\log_b n} } b^t - \sum_{t \mathop = 1}^{\floor {\log_b n} } 1\)
\(\ds \) \(=\) \(\ds \sum_{t \mathop = 1}^{\floor {\log_b n} } b^t - \floor {\log_b n}\)
\(\ds \) \(=\) \(\ds b \sum_{t \mathop = 0}^{\floor {\log_b n} - 1} b^t - \floor {\log_b n}\) extracting $b$ as a factor
\(\ds \) \(=\) \(\ds b \frac {b^{\floor {\log_b n} } - 1} {b - 1} - \floor {\log_b n}\) Sum of Geometric Progression
\(\ds \) \(=\) \(\ds \frac {b^{\floor {\log_b n} + 1} - b} {b - 1} - \floor {\log_b n}\)

The result follows by substituting $S$ back into $(1)$ and factoring out $\floor {\log_b n}$.

$\blacksquare$


Sources

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