4
$\begingroup$

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.

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

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)}. $$

$\endgroup$
  • $\begingroup$ Sorry, i was wrong here. Let me check it. $\endgroup$ – xbh Sep 4 '18 at 5:19
  • $\begingroup$ 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? $\endgroup$ – Cyc Sep 4 '18 at 5:22
  • 1
    $\begingroup$ @Cyc Sorry, let me check it. $\endgroup$ – xbh Sep 4 '18 at 5:27
  • $\begingroup$ Ignore my last comment, you made the fix right as I was posting :) Answer looks good after edits, well done. $\endgroup$ – Brevan Ellefsen Sep 4 '18 at 5:54
  • 1
    $\begingroup$ Thanks for compliment! Glad to help! $\endgroup$ – xbh Sep 4 '18 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.