Calculate the sum $S_n = \sum\limits_{k=1}^{\infty}\left\lfloor \frac{n}{2^k} + \frac{1}{2}\right\rfloor $

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.$$

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$.

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.$$