Closed form of sum with ceil of logarithm.

Question

I've been practicing discrete math recently and I'm stuck on this problem. Could someone help me with this, give me some hint or direction? The problem is:

Find the closed form of $\sum_{k=1}^n \lceil{log_{2}k}\rceil$

Thank you in advance!

Answer 1

Let $p=\lfloor\log_2{n}\rfloor$, then \begin{align*} \sum_{k=1}^n \lceil \log_2{k} \rceil&=\sum_{k=1}^{2^0}\lceil \log_2{k} \rceil+\sum_{k=2^0+1}^{2^1}\lceil \log_2{k} \rceil+\cdots+\sum_{k=2^{p-1}+1}^{2^p}\lceil \log_2{k} \rceil+\sum_{k=2^p+1}^n\lceil \log_2{k} \rceil\\ &=0+1\cdot\left(2^1-2^0\right)+2\cdot\left(2^2-2^1\right)+\cdots+p\cdot\left(2^p-2^{p-1}\right)+(p+1)\cdot \left(n-2^p\right)\\ &=1\cdot 2^0+2\cdot 2^1+\cdots +p\cdot 2^{p-1}+(p+1)\left(n-2^p\right)\\ &=\sum_{i=1}^pi\cdot 2^{i-1}+(p+1)\left(n-2^p\right)\\ &=(p-1)\cdot 2^p+(p+1)\left(n-2^p\right)+1 \end{align*} Here are some explanations \begin{align*} I&=\sum_{i=1}^pi\cdot 2^{i-1}\tag*{(1)}\\ 2I&=\sum_{i=1}^pi\cdot 2^{i}\tag*{(2)} \end{align*} You can make a difference between these two equations, then \begin{align*} -I&=\sum_{i=0}^{p-1}2^{i}-p\cdot 2^p=(1-p)\cdot 2^p-1\\ I&=(p-1)\cdot 2^p+1 \end{align*} So the proof is done.

Answer 2

Observation being part of science, doing what @Jean Marie suggested in comments, the first $\lceil \log_2 (k)\rceil$ are $$\{0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5\}$$ and the partial sums $$S_n=\sum_{k=1}^n \lceil{\log_{2}k}\rceil$$ are $$\{0,1,3,5,8,11,14,17,21,25,29,33,37,41,45,49,54,59,64,69\}$$ which are no more than

$$S_n=n \lceil \log_2 (n)\rceil -2^{\lceil \log_2 (n)\rceil }+1$$

$S_n$ is in fact the number of digits in the binary representation of all the numbers $1$ to $(n-1)$.

These numbers form sequence $A001855$ in $OEIS$ where you could find much more information.