# Value of $\lim_{n\to \infty} \frac{1}{2^n} \sum_{k=1}^{2^n} \{\log_{2}k\}$

Is there a closed form expression of $$\lim_{n\to \infty} \frac{1}{2^n} \sum_{k=1}^{2^n} \{\log_{2}k\}$$ , where $\{x\}=x-\lfloor x \rfloor$ denotes the fractional part of $x$? $\text{I think this limit will converge to a point between$0$and$\log_{2}3-1$}$
by $(x+y)(x-y)=(x^2-y^2)$, but I can't go further.

• doubt , is k taking values such as $k=2^0,2^1,\cdots , 2^n$, or something else? – Subhajit Halder Sep 4 '18 at 4:59
• Try $\{\log_2(k)\} = \{\log_2(k) - n\} = \{\log_2(k/2^n)\}$, then use Riemann integral. – xbh Sep 4 '18 at 5:02
• @GoodDeeds That substitution gives the difference of two divergent limits.. – Cyc Sep 4 '18 at 5:04
• @SubhajitHalder k takes all the integers between 1 and 2^n, of course. – Cyc Sep 4 '18 at 5:06

By periodicity, $\log_2 (k)$ and $\log_2 (k) - n$ has the same fractional part. Hence \begin{align*} \lim_n \frac 1{2^n} \sum_1^{2^n} \{\log_2(k)\} &= \lim_n \frac 1{2^n} \sum_1^{2^n} \left\{\log_2 \left(\frac k{2^n}\right) \right\} \\&= \lim_n \frac 1{2^n} \sum_1^{2^n} \log_2 \left( \frac k{2^n }\right) - \left\lfloor \log_2\left(\frac k{2^n}\right)\right\rfloor \\ &= \int_0^1 \log_2(x) \mathrm dx - \lim f(n)/2^n, \end{align*} where $$f(n) = \sum_1^{2^n} \lfloor \log_2(k/2^n)\rfloor = \sum_1^{2^n} \lfloor \log_2(k)\rfloor - 2^n \cdot n.$$ Now calculate the sum of the integer parts. Since $\lfloor \log_2(k)\rfloor = j$ when $2^j \leq k \leq 2^{j+1}-1$, we have $$f(n) + 2^n \cdot n = 0 + n + \sum_0^{n-1} 2^j j.$$ Let $S(n) = \sum_0^{n-1}j 2^j$, then $2S(n) = \sum_0^{n-1} 2^{j+1} j = \sum_1^n 2^j (j-1)$, thus \begin{align*} S(n) = 2S(n) - S(n) &= \sum_1^n 2^j (j-1) - \sum_0^{n-1} 2^j j= \sum_2^n 2^j (j-1) - \sum_1^{n-1} 2^j j \\ &= 2^n (n-1) + \sum_2^{n-1} 2^j (-1) -2 = 2^n (n-1) -2(2^{n-1}-1) \\ &= 2^n(n-2) +2, \end{align*} then $$\frac {f(n)}{2^n} = \frac {2^n (n-2) + 2 - 2^n n-n}{2^n} = -2 +\frac {2-n}{2^n} \to -2.$$ Hence the result is $$\int_0^1 \log_2 (x)\mathrm d x + 2 = 2 - \frac 1 {\log(2)}.$$
• How did you get the second equality? $1\leq k \leq 2^n$ only gives $-n \leq \log_{2} \left( \frac{k}{2^n} \right) \leq 0$. How did you remove the fractional part function? – Cyc Sep 4 '18 at 5:22