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

Solution 1:

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

Solution 2:

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