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

1 Answer 1

13
$\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$
9
  • $\begingroup$ Sorry, i was wrong here. Let me check it. $\endgroup$
    – xbh
    Commented Sep 4, 2018 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
    Commented Sep 4, 2018 at 5:22
  • 1
    $\begingroup$ @Cyc Sorry, let me check it. $\endgroup$
    – xbh
    Commented Sep 4, 2018 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$ Commented Sep 4, 2018 at 5:54
  • 1
    $\begingroup$ Thanks for compliment! Glad to help! $\endgroup$
    – xbh
    Commented Sep 4, 2018 at 6:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .