Sum of (Almost) Infinite Geometric Series

Question

I have recently stumbled upon this old problem of proving that $$ \displaystyle\sum_{k=0}^{\infty} \left\lfloor\dfrac{n+2^k}{2^{k+1}}\right\rfloor=n, \, \forall n\in \mathbb{Z}_+ $$ where $\left\lfloor x \right\rfloor$ denotes the greatest integer function of $x$.

One possible solution was using the fact that $\left\lfloor 2x\right\rfloor = \left\lfloor x\right\rfloor+\left\lfloor x+\frac{1}{2}\right\rfloor$, but that is not the solution I am looking for. I remember it had something to do with $\dfrac{n}{2}+\dfrac{n}{4}+\dfrac{n}{8}+\cdots= n$.

Answer 1

Let the binary representation of $n$ be $b_4b_3b_2b_1b_0$. Every term in the sum is the rounding of $n$ when you move the fractional point to the left. In other words, when you drop the rightmost digits but add the leftmost of them.

So the sum is

$$\begin{align}b_4b_3b_2b_1+b_0+\\b_4b_3b_2+b_1+\\b_4b_3+b_2+\\b_4+b_3+\\b_4\ \ \ \end{align}$$

We can rearrange this as

$$\begin{align}b_4b_4b_4b_4+b_4+\\b_3b_3b_3+b_3+\\b_2b_2+b_2+\\b_1+b_1+\\b_0\ \ \ \end{align}$$

or

$$\begin{align}b_40000+\\b_3000+\\b_200+\\b_10+\\b_0\ \ \end{align}$$

Answer 2

For $n \in \mathbb{Z}_+$, suppose $2^m\le n <2^{m+1}$ where $m\in \mathbb{N}$.

Then for $k\ge m+1$, $$ 0<\frac{n}{2^{k+1}}+\frac{1}{2}<1 $$ which leads to $\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor=0,\,\forall k\ge m+1$.

Thus, \begin{align} \sum_{k\ge0}\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor &= \sum_{k=0}^{m}\left\lfloor \frac{n}{2^{k+1}}+\frac{1}{2} \right\rfloor \\ &= \sum_{k=0}^{m}\left\lfloor \frac{n}{2^{k}} \right\rfloor - \sum_{k=0}^{m}\left\lfloor\frac{n}{2^{k+1}} \right\rfloor \\ &= \sum_{k=0}^{m}\left\lfloor \frac{n}{2^{k}} \right\rfloor - \sum_{k=1}^{m+1}\left\lfloor\frac{n}{2^{k}} \right\rfloor \\ &= \left(n+\sum_{k=1}^{m}\left\lfloor \frac{n}{2^{k}} \right\rfloor \right) - \left(\sum_{k=1}^{m}\left\lfloor\frac{n}{2^{k}} \right\rfloor + \left\lfloor \frac{n}{2^{m+1}} \right\rfloor\right) \\ &= n-\left\lfloor \frac{n}{2^{m+1}} \right\rfloor \\ &= n \end{align}

In the process we use the property $ \left\lfloor n+\frac{1}{2} \right\rfloor =\left\lfloor 2n \right\rfloor -\left\lfloor n \right\rfloor $.