# Sum of (Almost) Infinite Geometric Series

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

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}

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

• Sorry, I didn't see your requirement at first. As for the method of not using the property $\left\lfloor n+\frac{1}{2} \right\rfloor =\left\lfloor 2n \right\rfloor -\left\lfloor n \right\rfloor$, you can see another answer. – Zero Mar 16 at 16:09