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
    Apr 20, 2021 at 17:26

1 Answer 1

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
    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$ 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
    Apr 20, 2021 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.