Calculate the sum $S_n = \sum\limits_{k=1}^{\infty}\left\lfloor \frac{n}{2^k} + \frac{1}{2}\right\rfloor $ I am doing tasks from Concrete Mathematics by Knuth, Graham, Patashnik for trainning, but there are a lot of really tricky sums like that: 
Calculate sum $$S_n = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor  $$
My idea
I had the idea to check when  $$\frac{n}{2^k} < \frac{1}{2}$$
because then $$ \forall_{k_0 \le k} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor=0$$
It should be $$ k_0 = \log_2(2n) $$ but I don't know how it helps me with this task (because I need not only "stop moment" but also sum of considered elements
Book idea

Let $$S_n = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor $$
then $$ S_n-S_{n-1} = 1$$

and then solve this recursion. But I write $S_n - S_{n-1}$ and  I don't see how it can be $1$ , especially that is an infinite sum.

Let
$$2^{b}\le n<2^{b+1}$$
For all $1\le k\le b$,
$$\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor=\frac{2^b}{2^k}+\left\lfloor\frac{n-2^b}{2^k}+\frac12\right\rfloor.$$
For $k=b+1$,
$$\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor=1.$$
And for $k>b+1$,
$$\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor=0.$$
This allows us to write, by summing,
$$S_n=2^{b-1}+2^{b-2}+\cdots 2^0+1+S_{n-2^b}=2^b+S_{n-2^b},$$
which shows that $n$ and $S_n$ share the same binary representation.
E.g., inductively,
$$S_{123}=64+S_{59}=64+32+S_{27}=64+32+16+S_{11}\\\cdots\\=64+32+16+8+2+1.$$
