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?
Best Answer
$$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<x<(y+0.5)^2 \text{except for $y=0$ which only happens for $x=0$ or $x=1$.} $$ $$\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<x\leq(y+1)^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<x\leq(y+1.5)^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$.