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?
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?
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. \]