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.