Can You Prove the Floor Function Challenge for Real Numbers?

[anemone]

For all real $x$, prove that $\displaystyle\sum_{k=0}^{\infty} \left\lfloor\dfrac{x+2^k}{2^{k+1}}\right\rfloor=\lfloor x\rfloor$.

 

[Nono713]

Yes, it's supposed to be a sum, not a limit, in case anyone else was confused (can't believe nobody pointed it out).

 

[anemone]

Hi Bacterius,

Yep, you're right...sorry for making such a silly typo and thanks for pointing it out!

I've just fixed the typo. Thanks again.:)

 

[Euge]

Spoiler

Let $x$ be real, $n = \lfloor{x}\rfloor$, and for all integers $k \ge 0$ set

$A(k) = \left\lfloor{\frac{n+1}{2}}\right\rfloor + \left\lfloor{\frac{n+2}{4}}\right\rfloor + \cdots + \left\lfloor{\frac{n+2^k}{2^{k+1}}}\right\rfloor + \left\lfloor{\frac{n}{2^{k+1}}}\right\rfloor.$

Since $\left\lfloor{\frac{n}{2^{k+1}}}\right\rfloor$ is always an integer,

$\left\lfloor{\frac{n}{2^{k+1}}}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor{\frac{n}{2^{k+1}}}\right\rfloor+1}{2}}\right\rfloor + \left\lfloor{\dfrac{\left\lfloor{\frac{n}{2^{k+1}}}\right\rfloor}{2}}\right\rfloor = \left\lfloor{\dfrac{\frac{n}{2^{k+1}}+1}{2}}\right\rfloor + \left\lfloor{\dfrac{\frac{n}{2^{k+1}}}{2}}\right\rfloor = \left\lfloor{\frac{n+2^{k+1}}{2^{k+2}}}\right\rfloor + \left\lfloor{\frac{n}{2^{k+2}}}\right\rfloor.$

Therefore $A(k+1) = A(k)$ for all $k$, i.e., $A(k)$ is constant. The value of the constant is

$A(0) = \left\lfloor{\frac{n+1}{2}}\right\rfloor + \left\lfloor{\frac{n}{2}}\right\rfloor = n$,

since $n$ is an integer. Thus $A(k) = n$ for all $k \ge 0$. Let $2^{k_0}$ is the highest power of $2$ not exceeding $n$. For all $k \ge k_0$, $\left\lfloor{n/2^{k+1}}\right\rfloor = 0$ and thus

$n = A(k) = \left\lfloor{\frac{n+1}{2}}\right\rfloor + \left\lfloor{\frac{n+2}{4}}\right\rfloor + \cdots + \left\lfloor{\frac{n+2^k}{2^{k+1}}}\right\rfloor.$

This shows that

$\sum_{k = 0}^\infty
\left\lfloor{\frac{n+2^k}{2^{k+1}}}\right\rfloor = n.$

Since for each $k \ge 0$,

$\left\lfloor{\frac{n+2^k}{2^{k+1}}}\right\rfloor =\left\lfloor{\frac{x+2^k}{2^{k+1}}}\right\rfloor$,

it is also the case that

$\sum_{k = 0}^\infty \left\lfloor{\frac{x+2^k}{2^{k+1}}}\right\rfloor = n.$

 

[anemone]

Thanks, Euge for participating in this challenge problem.:) Your proof is great!

Here is the solution uses the Hermite's identity in the proof:

Spoiler

From the Hermite Identity, we have $\displaystyle\sum_{k=0}^{n-1} \left\lfloor x+\dfrac{k}{n}\right\rfloor=\lfloor nx\rfloor$ and taking $n=2$ we then have

$\displaystyle\sum_{k=0}^{1} \left\lfloor x+\dfrac{k}{2}\right\rfloor=\lfloor 2x\rfloor$

i.e. $\left\lfloor x\right\rfloor+\left\lfloor x+\dfrac{1}{2}\right\rfloor=\lfloor 2x\rfloor$ and rewriting to make $\displaystyle \left\lfloor x+\dfrac{1}{2}\right\rfloor$ as the subject gives

$\displaystyle \left\lfloor x+\dfrac{1}{2}\right\rfloor=\lfloor 2x\rfloor-\left\lfloor x\right\rfloor$

Note that we can make full use of this identity, as we can have

$\displaystyle \left\lfloor \dfrac{x}{2}+\dfrac{1}{2}\right\rfloor=\lfloor x\rfloor-\left\lfloor \dfrac{x}{2}\right\rfloor$

$\displaystyle \left\lfloor \dfrac{x}{4}+\dfrac{1}{2}\right\rfloor=\left\lfloor \dfrac{x}{2}\right\rfloor-\left\lfloor \dfrac{x}{4}\right\rfloor$

and so on and so forth.

Now, back to the question, expand the sum given in sigma notation into an explicit sum yields:

$\displaystyle\sum_{k=0}^{\infty} \left\lfloor\dfrac{x+2^k}{2^{k+1}}\right\rfloor$

$=\left\lfloor\dfrac{x+1}{2}\right\rfloor+\left\lfloor\dfrac{x+2}{4}\right\rfloor+\left\lfloor\dfrac{x+4}{8}\right\rfloor+\cdots$

$=\left\lfloor\dfrac{x}{2}+\dfrac{1}{2}\right\rfloor+\left\lfloor\dfrac{x}{4}+\dfrac{1}{2}\right\rfloor+\left\lfloor\dfrac{x}{8}+\dfrac{1}{2}\right\rfloor+\cdots$

$=\left\lfloor x\right\rfloor-\left\lfloor \dfrac{x}{2}\right\rfloor+\left\lfloor \dfrac{x}{2}\right\rfloor-\left\lfloor \dfrac{x}{4}\right\rfloor+\left\lfloor \dfrac{x}{4}\right\rfloor-\left\lfloor \dfrac{x}{8}\right\rfloor+\cdots$

$=\left\lfloor x\right\rfloor-\cancel{\left\lfloor \dfrac{x}{2}\right\rfloor}+\cancel{\left\lfloor \dfrac{x}{2}\right\rfloor}-\cancel{\left\lfloor \dfrac{x}{4}\right\rfloor}+\cancel{\left\lfloor \dfrac{x}{4}\right\rfloor}-\cancel{\left\lfloor \dfrac{x}{8}\right\rfloor}+\cdots$

$=\left\lfloor x\right\rfloor$

and we're done.