0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Piquito Oct 23 '16 at 22:58
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.