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.

Consider how $\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ depends on the binary representation of $n$. Dividing by $2^k$ shifts the digits to the right by $k$. There are then two cases:


*

*If the $k^{th}$ binary digit of $n$ is $0$, then adding $1/2$ will not cause a carry, so $\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ is just equal to the truncation of $n/2^k$ after the decimal point.

*If the $k^{th}$ binary digit of $n$ is $1$, then adding $1/2$ will cause a carry, so $\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ is just equal to this truncation plus one.
Now, letting $f_k(n)=\left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor$ for brevity, consider the difference between $f_k(n)$ and $f_k(n-1)$. The difference between the binary representations of $n$ and $n-1$ is summarized as follows; if $n$ has $t$ trailing zeroes, then $n$ ends with $100\dots0$, while $n-1$ ends with $011\dots1$. Otherwise, the representations are the same.


*

*If $k>t+1$, then $f_k(n)=f_k(n-1)$, since the binary representations of $n$ and $n-1$ are equal after the first $t+1$ places, and the first $t+1$ places do not affect the computation of $f_k(n)$ and $f_k(n-1)$.

*If $k=t+1$, then $f_k(n)=f_k(n-1)+1$. The former has a carry, while the latter does not.

*If $k<t+1$, then $f_k(n)=f_k(n-1)$. The latter will have a carry, and the former will not. You can verify this on your own with some examples. 
Therefore, in
$$
S_n-S_{n-1}=\sum_{k=1}^\infty \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor-\left\lfloor \frac{n-1}{2^k} + \frac{1}{2} \right\rfloor
$$
exactly one summand is equal to $1$ and the rest are zero, so $S_n-S_{n-1}=1$. 
