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.
 A: Here we use a technique which is introduced in section 3.2 Floor/Ceiling    Applications of OPs referred book Concrete Mathematics
by R. L. Graham, D. E. Knuth and O. Patashnik. We show the following is valid for $n\in\mathbb{Z}, n>0$:
\begin{align*}
\color{blue}{\sum_{k=1}^\infty\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor=n}\tag{1}
\end{align*}

Let $n=\sum_{j=0}^Na_j2^j$ be the binary representation of $n$ with $a_j\in\{0,1\}, 0\leq j\leq N$. We obtain
  \begin{align*}
\color{blue}{\sum_{k=1}^\infty}\color{blue}{\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor}
&=\sum_{k=1}^\infty\sum_{m=1}^\infty   m\left[m=\left\lfloor\frac{n}{2^k}+\frac{1}{2}\right\rfloor\right]\tag{2}\\
&=\sum_{k=1}^\infty\sum_{m=1}^\infty m\left[m\leq   \frac{n}{2^k}+\frac{1}{2}<m+1\right]\tag{3}\\
&=\sum_{k=1}^\infty\sum_{m=1}^\infty m\left[m-\frac{1}{2}\leq\frac{1}{2^k}\sum_{j=0}^Na_j2^j<m+\frac{1}{2}\right]\tag{4}\\
&=\sum_{j=0}^Na_j\sum_{k=1}^{j+1}\sum_{m=1}^\infty m\left[m-\frac{1}{2}\leq 2^{j-k}<m+\frac{1}{2}\right]\tag{5}\\
&=\sum_{j=0}^Na_j\left(\sum_{k=1}^j2^{j-k}+1\right)\tag{6}\\
&=\sum_{j=0}^N a_j\left(\sum_{k=0}^{j-1}2^k+1\right)\tag{7}\\
&=\sum_{j=0}^Na_j 2^j\tag{8}\\
&\,\,\color{blue}{=n}
\end{align*}
  and  the claim (1) follows.

Comment:


*

*In (2) we introduce a series  summing over $m$ and use Iverson brackets to get rid of the floor-function. Note the smallest value which might contribute to the sum is $m=1$.

*In (3) we use an equivalent representation of the floor function.

*In (4) we rearrange the inequality chain inside the Iverson brackets and use the binary representation of $n$.

*In (5) we use the linearity of the $\sum$ operator. We also restrict the upper limit of the second left-most sum with $k=j+1$ since other values of $k$ do not contribute.

*In (6) we observe that $m$ takes the value $2^{j-k}$ iff $1\leq k\leq j$ and $m=1$ if $k=j+1$.

*In (7) we shift the index by one to start with $k=0$ and we also change to order of summation $k\to j-1-k$.

*In (8) we use the finite geometric series formula $\sum_{k=0}^{j-1}2^k=\frac{2^j-1}{2-1}=2^j-1$ and get the binary representation of $n$.
A: 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.$$
A: 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.$$
A: 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$. 
A: 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$$
