0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Zero Mar 16 at 16:09

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.