# How to prove equality between these two expressions containing floor and ceiling functions?

I'm trying to simplify the following expression:

$$2 y + \lceil \frac{x - y(y + 1)}{y + 1} \rceil + 1$$

where

$$y = \lfloor \frac{\sqrt{4x + 1} - 1}{2} \rfloor$$

(I deliberately cut up the expression using $$y$$ for readability, do tell me if I shouldn't.)

The problem is I think this expression should be equal to $$\lceil 2 \sqrt{x} \rceil$$ for any integers x, but I'm not able to prove it. The values for the first $$2^{64}$$ integers correspond, but this is of course no formal proof. I'm stuck at the moment at expression:

$$\lceil \frac{x}{y} \rceil + y$$

where

$$y = \lfloor \frac{\sqrt{4x + 1} + 1}{2} \rfloor$$

although this may be a dead end.

I guess my question also includes the more general question: how does one prove an equality between two expressions with variable $$x \in \mathbb{N}$$ containing floor and ceiling functions?

• If $x = 0$ then $y = 0$ and the expression is $2\lfloor \sqrt x \rfloor + 1 = 1$. and not $2\rceil \sqrt x\rceil=0$. Of course $\lfloor m \rfloor + 1 = \lceil m \rceil$ if $m$ is not an integer. And $4x+1$ and $x$ can't both be perfect squares unless $x = 0$. Apr 20, 2021 at 17:26

$$y=\lfloor \frac{\sqrt{4x+1}-1}2 \rfloor$$ $$\frac{\sqrt{4x+1}-1}2 \in \Big[y,y+1\Big)$$ $$\frac{\sqrt{4x+1}}2 \in \Big[y+\frac12, y+\frac32\Big)$$ $$\sqrt{x+\frac14} \in \Big[y+\frac12, y+\frac32\Big)$$ $$x+\frac14 \in \Big[(y+1/2)^2,(y+3/2)^2\Big)$$ $$x \in \Big[(y)(y+1),(y+1)(y+2)\Big)$$ You can see that this perfectly partitions all values of $$x$$, as these intervals do not overlap for distinct integer values of $$y$$. $$x=(y+1)(y+k), k \in \Big[0,2\Big)$$ $$2y+\lceil\frac{x-y(y+1)}{y+1}\rceil+1 = 2y+\lceil k \rceil+1$$ Let's do some casework:
If $$k=0$$: $$x=y^2+y$$ $$y^2 $$\lceil 2\sqrt{x} \rceil = 2y+1 = 2y+\lceil k \rceil+1 = 2y+\lceil\frac{x-y(y+1)}{y+1}\rceil+1$$ If $$k \in \Big(0,1\Big]$$: $$x \in (y^2+y,y^2+2y+1]$$ $$x \in [y^2+y+1,y^2+2y+1] \text{ as } x \text{ is an integer.}$$ $$(y+0.5)^2 $$\lceil 2\sqrt{x} \rceil = 2y+2 = 2y+\lceil k \rceil+1 = 2y+\lceil\frac{x-y(y+1)}{y+1}\rceil+1$$ If $$k \in \Big(1,2\Big)$$: $$x \in (y^2+2y+1,y^2+3y+2)$$ $$x \in [y^2+2y+2,y^2+3y+1]] \text{ as } x \text{ is an integer.}$$ $$(y+1)^2 $$\lceil 2\sqrt{x} \rceil = 2y+3 = 2y+\lceil k \rceil+1 = 2y+\lceil\frac{x-y(y+1)}{y+1}\rceil+1$$ Therefore $$\lceil 2\sqrt{x} \rceil = 2y+\lceil\frac{x-y(y+1)}{y+1}\rceil+1$$ for all positive integer values of $$x$$.
• Thanks but there is a mistake somewhere since your conclusion is false. Indeed, after some testing, this results in different results for (seemingly) any value of $x$. The equality seems to be between $\lceil 2 \sqrt{x} \rceil$ and $2y + \lceil \frac{x - y(y+1)}{y+1} \rceil + 1$, and not $y + \lceil \frac{x - y(y+1)}{y+1} \rceil + 1$. Your answer does however give a nice answer to my question as to how one should proceed with expressions of this form. I'm looking for the mistake currently, maybe it's just a small one. Apr 20, 2021 at 9:02
• Indeed, all this seems correct. I edited the typo as well as added in a special case for when $k=0$ (the case when $y=0$). Thanks for the thorough explanation! Apr 20, 2021 at 14:01