This is a problem from the book Concrete Mathematics. It is about finding a closed formula for a sum. I came up with one but when checking with values of the sum at different points the formula fails. Any help would be appreciated
(since there is a lot of text I know not all steps will be very clear so I'll try to explain whenever someone tells me it's necessary)
lg(k) = Base two logarithm.
$\lceil k \rceil$ is the usual ceiling function and $\lfloor k \rfloor$ is the floor function
$$\sum_{k=1}^n \lceil lg(k)\rceil = \sum_{k,m \ge 0} m[1 \le k\le n][m = \lceil lg(k)\rceil ] = \sum_{k,m \ge 0} m[1 \le k\le n][m-1 \lt lg(k) \le m]$$
$$=\sum_{k,m \ge 0} m[1 \le k\le n][2^{m-1} \lt k \le 2^m]$$
$$=\sum_{k,m \ge 0} m[2^{m-1} \lt k \le 2^m \le n] + \sum_{k,m \ge 0} m[2^{m-1} \lt k \le n \lt 2^m] = S_1 + S_2 $$
I think the mistake might be in this last derivation when splitting the sum in two. Let's try to find a closed formula for both of these sums :
$$S_1 =\sum_{k,m \ge 0} m[2^{m-1} \lt k \le 2^m \le n] = \sum_{m \ge 0} m(2^m - 2^{m-1})[2^m \le n] = \sum_{m \ge 0} m\cdot2^{m-1}[m \le lg(n)] = \sum_{m \ge 0} m\cdot2^{m-1}[m \le \lfloor lg(n) \rfloor] = \frac 12 \sum_{m=0}^{\lfloor lg(n) \rfloor}m2^m$$
Through trial and error I found that, for $f(x) = (x-2)2^x, \Delta f(x) = x2^x$
For a little bit of tidyness I'll call $\lfloor lg(n) \rfloor = Z$
So our sum can be rewritten as follows
$$ \frac 12 \sum_{m=0}^Zm2^m = \frac 12 \sum_0^{Z + 1} x2^x dx = \frac 12 \Bigl( f(Z + 1) - f(0) \Bigr) = (Z -1)2^{Z} + 1 $$
Now I'll go through the other sum which will be split in two again
$$S_2 =\sum_{k,m \ge 0} m[2^{m-1} \lt k \le n \lt 2^m] = \sum_{m \ge 0} m(n-2^{m-1})[2^{m-1} \lt n] = \sum_{m \ge 0} m(n-2^{m-1})[2^{m-1} \lt n] = \sum_{m \ge 0} m(n-2^{m-1})[2^{m-1} \le n] $$
$$\text{ (we should be able to add $2^{m-1} = n$ here since the term in the sum for that particular value is 0) } $$
$$\sum_{m \ge 0} m(n-2^{m-1})[2^{m-1} \le n] = \sum_{m \ge 0} m(n-2^{m-1})[m-1 \le lg(n)] = \sum_{m \ge 0} m(n-2^{m-1})[m-1 \le \lfloor lg(n) \rfloor] = \sum_{m \ge 0} m(n-2^{m-1})[m-1 \le Z] = \sum_{m \ge 0} m(n-2^{m-1})[m \le Z + 1] = \sum_{m = 0}^{Z+1} m(n-2^{m-1}) = n \sum_{m = 0}^{Z+1} m - \frac 12 \sum_{m = 0}^{Z+1} m2^m $$
We know the discrete antiderivative for both sums (the first one is a falling factorial power and the second one was found previously)
So we get
$$n \sum_{m = 0}^{Z+1} m - \frac 12 \sum_{m = 0}^{Z+1} m2^m = \frac {n(Z+1)(Z+2)}{2} - \frac 12 \Bigl( f(Z+2) - f(0) \Bigr) = \frac {n(Z+1)(Z+2)}{2} - (Z2^{Z+1} + 1)$$
So the closed form for this sum is $$\sum_{k=1}^n \lceil lg(k)\rceil =(Z -1)2^{Z} + 1 + \frac {n(Z+1)(Z+2)}{2} - (Z2^{Z+1} + 1) $$
This is however incorrect when checking with the values of the sum
I know how to find a formula now since the book provides a really easy method for calculating it. I just want to know where I made a mistake. Thanks in advance