<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] Since $S_1=1$ try to prove that $S_n=n$ by induction. Note that if $n=2m$ is even
$$\begin{align*}
S_n=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor
&=\sum_{k=1}^{\infty}\left\lfloor\frac{2m}{2^k}+\frac12\right\rfloor
=\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac12\right\rfloor\\
&=\left\lfloor m+\frac12\right\rfloor +\sum_{k=2}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac12\right\rfloor\\
&=\left\lfloor m+\frac12\right\rfloor +\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k}}+\frac12\right\rfloor=m+S_m=m+m=n
\end{align*}$$
On the other hand if $n=2m+1$, then
$$\begin{align*}
S_n=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{2^k}+\frac12\right\rfloor
&=\sum_{k=1}^{\infty}\left\lfloor\frac{2m+1}{2^k}+\frac12\right\rfloor
=\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac{1}{2^{k}}+\frac12\right\rfloor\\
&=\left\lfloor m+\frac12+\frac12\right\rfloor +\sum_{k=2}^{\infty}\left\lfloor\frac{m}{2^{k-1}}+\frac{1}{2^{k}}+\frac12\right\rfloor\\
&=m+1+\sum_{k=1}^{\infty}\left\lfloor\frac{m}{2^{k}}+\frac{1}{2^{k+1}}+\frac12\right\rfloor\\
&=m+1+S_m=m+1+m=n.
\end{align*}$$
where it remains to show that for all $k\geq 1$,
$$\left\lfloor\frac{m}{2^{k}}+\frac{1}{2^{k+1}}+\frac12\right\rfloor=\left\lfloor\frac{m}{2^{k}}+\frac12\right\rfloor.$$
Can you show this last step?
P.S. Actually $S_n$ is a finite sum. If $n<2^{N}$ then $\frac{n}{2^{N+1}}<\frac12$ and $\left\lfloor \frac{n}{2^{N+1}} + \frac12 \right\rfloor=0$. Hence
$$S_n = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{2^k} + \frac12 \right\rfloor=\sum_{k=1}^{N} \left\lfloor \frac{n}{2^k} + \frac12 \right\rfloor.$$
</s>