# Floor function sum identity

Prove, that

$$\sum_{n=1}^{N} \left \lfloor{\frac{x}{2^{n}}+\frac{1}{2}}\right \rfloor =\left \lfloor{x}\right \rfloor$$ for large enough N.

It's easy to see that addents start to vanish at some point (it's possible to calculate for which n it takes place). But I can't say much more about this proof so any help would be nice.

Let $x=-3.5$. Then we have

$$\sum_{n\ge 1}\left\lfloor\frac{-3.5}{2^n}+\frac12\right\rfloor=\lfloor-1.25\rfloor+\lfloor-0.375\rfloor+\lfloor0.0625\rfloor+\ldots=-2-1=-3\;,$$

but $\lfloor-3.5\rfloor=-4$. The result is clearly true for $x=0$, so I will assume that that $x>0$. Let $b_mb_{m-1}\ldots b_0.d_1d_2\ldots$ be the binary representation of $x$, so that

$$x=\sum_{k=0}^mb_k2^k+\sum_{k\ge 1}\frac{d_k}{2^k}\;.$$

For $n\ge 1$ let

$$x_n=\left\lfloor\frac{x}{2^n}+\frac12\right\rfloor\;;$$

then for $1\le n\le m$ we have $x_n=(b_m\ldots b_n)_{\text{two}}+b_{n-1}$, $x_{m+1}=b_m=1$, and $x_n=0$ for $n>m+1$. Thus, if $\beta(x)$ is the number of $1$ bits in the binary representation of $\lfloor x\rfloor$,

$$\sum_{n\ge 1}x_n=\sum_{n\ge 1}\left\lfloor\frac{x}{2^n}\right\rfloor+\beta(x)\;.$$

The binary representations of the terms $\left\lfloor\frac{x}{2^n}\right\rfloor$ for $1\le n\le m$ are shown in the following table.

$$\begin{array}{c|cc} n&&&\;\;\lfloor x/2^n\rfloor\\ \hline 1&b_m&b_{m-1}&b_{m-2}&\ldots&b_2&b_1\\ 2&&b_m&b_{m-1}&\ldots&b_3&b_2\\ 3&&&b_m&\ldots&b_4&b_3\\ &&&&\ddots&\vdots&\vdots\\ m-1&&&&&b_m&b_{m-1}\\ m&&&&&&b_m \end{array}$$

Note that for $k=1\ldots,m$, $b_k$ appears in the first $k$ rows, once in each of the rightmost $k$ positions, so it contributes altogether

$$b_k\sum_{i=0}^{k-1}2^i=\begin{cases} 2^k-1,&\text{if }b_k=1\\ 0,&\text{if }b_k=0\;. \end{cases}$$

to $\sum_{n\ge 1}\left\lfloor\frac{x}{2^n}\right\rfloor$. There are $\beta(x)-b_0$ values of $k\in\{1,\ldots,m\}$ such that $b_k=1$, so

\begin{align*} \sum_{n\ge 1}x_n&=\sum_{n\ge 1}\left\lfloor\frac{x}{2^n}\right\rfloor+\beta(x)\\\\ &=\sum_{\substack{1\le k\le m\\b_k=1}}\left(2^k-1\right)+\beta(x)\\\\ &=\sum_{\substack{1\le k\le m\\b_k=1}}2^k-\big(\beta(x)-b_0\big)+\beta(x)\\\\ &=(\lfloor x\rfloor-b_0)+b_0\\\\ &=\lfloor x\rfloor\;, \end{align*}

as desired.

• First: user EmEl put his comment "Fourth is not zero term" before my already written "You are wrong, dear friend" so I did not put my comment. Second: You work (with better English and better TeX Commands, of course) with the binary representation of $x$ before I finish the same way. (This happen to me many times in StackExchange). My respects. – Piquito Oct 23 '16 at 22:58

A quick check you can do is when some term $\left\lfloor\frac{x}{2^n}+\frac{1}{2}\right\rfloor$ in the left side increases. You should find that it increases exactly when $x$ becomes $2^{n-1}$ times an odd number. So when $x$ increases between integers, the left side doesn't increase at all and obviously neither does the right.

But when $x$ becomes an integer, there is a unique maximal power of $2$ that it is divisible by, and this term and this term alone increases. For example, if $x$ goes from $2.9$ to $3$, the term $\left\lfloor\frac{x}{2}+\frac{1}{2}\right\rfloor$ increases from $1$ to $2$, and none of the other terms increase. And if $x$ goes from $7.9$ to $8$, the term $\left\lfloor\frac{x}{16}+\frac{1}{2}\right\rfloor$ increases from $0$ to $1$ and no other term on the left increases at all.

So if at integers the left increases by 1 and nowhere else, this is exactly what the right is, since both are $0$ at $x=0$. So the left and right sides must be equal.

• Thank you, very nice solution. – EmEl Oct 23 '16 at 22:56