An identity with integer part of $\log_2$

Let $n \in \mathbb{N}$. Prove that:

$$\sum_{k=1}^{2^n} \left \lfloor \log_2 k \right \rfloor =\left ( n-2 \right )2^n +n +2$$

Solution

We note that:

\begin{align*}
\sum_{k=1}^{2^n} \left \lfloor \log_2 k \right \rfloor  &= \sum_{i=0}^{n-1} \sum_{k=2^i}^{2^{i+1}-1}\left [ \left \lfloor \log_2 k \right \rfloor + \left \lfloor \log_2 2^n \right \rfloor  \right ] \\
 &\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\overset{\left \lfloor \log_2 k \right \rfloor=i , \;\; \;2^i \leq k < 2^{i+1}}{=\! =\! =\! =\! =\! =\! =\! =\! =\! =\! =\! =\! =\! =\! } \sum_{i=0}^{n-1} i 2^i + \left \lfloor \log_2 2^n \right \rfloor \\
 &=\left ( n-2 \right ) 2^n +n +2
\end{align*}

The sum $\sum \limits_{i=0}^{n-1}i 2^i$ is just a geometric series.