0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – fleablood
    Commented Apr 20, 2021 at 17:26

1 Answer 1

Reset to default
1
$\begingroup$

$$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$.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – J. Schmidt
    Commented Apr 20, 2021 at 9:02
  • 1
    $\begingroup$ Ah, sorry, it was merely a typo in my work that got repeated after I copied and pasted the previous lines. The result is correct, however. $\endgroup$
    – Isaac Mammel
    Commented Apr 20, 2021 at 11:54
  • $\begingroup$ 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! $\endgroup$
    – J. Schmidt
    Commented Apr 20, 2021 at 14:01

You must log in to answer this question.

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