Prove that
$ f(n) = n - 1 + f(\lfloor {n/2} \rfloor) + f(\lceil n/2 \rceil)$ where $f(n) = \sum_1^n{\lceil{\log_2 k}\rceil}$
My trials:
At first I find a formula for $f(n)$. If $n = 2^m$ , then in the sum of $f(n) = \sum_1^n{\lceil{\log_2 k}\rceil}$ ,
$m$ appears $2^{m-1}$ times, $m-1$ appears $2^{m-2}$ times,... and so on, till $0$ appearing $1$ time, which gives $f(n) = \sum_1^m{j\cdot 2^{j-1}} = 2^m(m-1) + 1 $.
I want to show the given equation is true for values of $n = 2^m$ only at the moment. Upto this point I could do, but the proof of the given equation is getting a bit too hard for me.
Plugging in the value of $f(2n) = 2^{m+1}\cdot m + 1$ and calculating $2f(n) + n - 1 = 2^m (2m-1) + 1$ is not equalling. * <- OK its equalling, it should be $2f(n) + 2n - 1 = 2^m (2m-1) + 1$ in the second equation.
Instead, I would like to ask for a simpler proof of this identity using the identities $\lceil \log_2 2j \rceil$ = $\lceil \log_2 j \rceil + 1$ and $\lceil \log_2{(2j-1)}\rceil = \lceil \log_2 j \rceil + [j > 1]$, for $j>= 1$ because that's what the book really wants.
Note: this is problem 3.34 of Concrete Math. The hint uses finite calculus, but it also says it can be directly done using simpler logarithmic identities.