# Evaluate $\sum_{n=1}^{1024}\left \lfloor \log_2n \right \rfloor$.

Evaluate $\sum_{n=1}^{1024}\left \lfloor \log_2n \right \rfloor$.

I thought the answer is $1+1*2+2*2^2+3*2^3+4*2^4+5*2^5+6*2^6+7*2^7+8*2^8+9*2^9+2^{10}=9219$, but the answer should be 8204. What mistake have I made?

-
The first term should be $0 = 0 \cdot 2^0$ and the last term $10$. Then you get 1015 less, that is 8204. – martini Sep 28 '12 at 10:44
HAHA! I've just made a stupid mistake! Thanks martini. – ᴊ ᴀ s ᴏ ɴ Sep 28 '12 at 10:50

We have $\lfloor \log_2 n \rfloor = k$ iff $2^k \le n < 2^{k+1}$, so for $0 \le k \le 9$, $k$ appears in the above sum exactly $2^{k+1} - 2^k = 2^k$ times. As $10$ appears exactly once (for $n =1024$), we have $\sum_{n=1}^{1024} \lfloor \log_2 n \rfloor = 10 + \sum_{k=0}^9 k2^k = 8204.$
THANKS! ~ ${}{}{}$ – ᴊ ᴀ s ᴏ ɴ Sep 28 '12 at 13:17