Calculate $f(n)=\sum_{k=1}^n\lceil \lg k\rceil$ when $n>1$.
I can understand the solution from textbook, but I cant figure out why my solution gets wrong answer. Hope someone can point out my mistakes and help me to correct. My solution is as below:
Assume m=$\lceil \lg k\rceil$,
$$ \begin{aligned} f(n)&=\sum_{k=1}^n\lceil \lg k\rceil \\ &=\sum_{k,m\geq 1} m[k\leq n][m=\lceil \lg k\rceil] \\ &=\sum_{k,m\geq 1} m[k\leq n][m-1<\lg k\leq m] \\ &=\sum_{k,m\geq 1} m[k\leq n][2^{m-1}<k\leq 2^m] \\ &=\sum_{k,m\geq 1} m[2^{m-1}<k\leq 2^m\leq n]+\sum_{k,m\geq 1} m[2^{m-1}<k\leq n\leq 2^m] \end{aligned} $$
Assume $a=\lceil \lg n\rceil$,
The first part of RHS $$ \begin{aligned} &=\sum_{k,m\geq 1} m[2^{m-1}<k\leq 2^m\leq 2^a] \\ &=\sum_{m\geq 1}(2^{m-1}[m-1<a]) \\ &=\sum_1^{a+1} 2^{m-1}m\delta m=(a-1)2^a+1 \end{aligned} $$
The second part of RHS
$m=a$, $\sum_{k\geq 1} a[2^{a-1}<k\leq n\leq 2^a]=a(n-2^{a-1})$
Therefore, $f(n)=an+1+(a-1)2^a-a2^{a-1},a=\lceil \lg n\rceil$
The correct answer is $f(n)=(a-1)2^a+1+a(m-2^a)$. The only difference is $2^a$ and $2^{a-1}$ from the second part.