MHB Can You Prove the Floor Function Challenge for Real Numbers?

AI Thread Summary
The discussion revolves around proving the equation involving the floor function, specifically that the sum of the floor function from k=0 to infinity equals the floor of x for all real numbers x. Participants clarify that the expression is indeed a sum, not a limit, addressing initial confusion. A typo in the original post was corrected, and appreciation was expressed for contributions to the challenge. The solution incorporates Hermite's identity as part of the proof. Overall, the thread emphasizes collaboration in solving mathematical challenges.
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
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$.
 
Last edited:
Mathematics news on Phys.org
Yes, it's supposed to be a sum, not a limit, in case anyone else was confused (can't believe nobody pointed it out).
 
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.:)
 
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.$
 
Thanks, Euge for participating in this challenge problem.:) Your proof is great!

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

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.
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Thread 'Imaginary Pythagorus'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top