<s>[INST] 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.
 [/INST] From $\left\lfloor x+\frac{1}{2}\right\rfloor=\lfloor 2x\rfloor-\lfloor x\rfloor$ we have
$$\left\lfloor \frac{n}{2^k}+\frac{1}{2}\right\rfloor=\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lfloor \frac{n}{2^k}\right\rfloor$$
therefore
$$\sum_{k=1}^\infty \left\lfloor \frac{n}{2^k}+\frac{1}{2}\right\rfloor=\sum_{k=1}^\infty
\left\lfloor \frac{n}{2^{k-1}}\right\rfloor-\left\lfloor \frac{n}{2^k}\right\rfloor\\
=\lfloor n\rfloor -\lim_{k\to \infty}\left\lfloor \frac{n}{2^k}\right\rfloor\\=n$$
</s>