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$

2 Answers 2

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$
1
  • $\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$
    – Chiquita
    Mar 16, 2019 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .