The floor of $\sqrt{2x}+1/2$ is the ceiling of $(\sqrt{1+8x}-1)/2$

Question

I've been working on this for a while now and I can't figure out how to prove it: $$\left\lfloor \sqrt{2x} + \frac{1}{2}\right\rfloor = \left\lceil \frac{\sqrt{1+8x}-1}{2}\right\rceil.$$

Here $x$ is an integer.

Answer 1

The result holds for every positive integer $x$.

Back to the definitions. Call $A_x$ and $B_x$ the LHS and the RHS of the relation to prove. Then $A_x=n$ if and only if $n$ is an integer and $$ n\le\sqrt{2x}+\textstyle{\frac12}<n+1. $$ This translates as $$ n^2-n+\textstyle{\frac14}\le2x<n^2+n+\textstyle{\frac14}, $$ that is, $a(n)\le\frac12(\sqrt{1+8x}-1)<b(n)$ with $$ a(n)=\sqrt{n^2-n+\textstyle{\frac12}}-\textstyle{\frac12},\qquad b(n)=\sqrt{n^2+n+\textstyle{\frac12}}-\textstyle{\frac12}. $$ Since $a(n)>n-1$, $B_x\ge n$. Since $b(n)<n+1$, $B_x\le n+1$, hence $B_x=n$ or $n+1$. But $b(n)>n$ hence our double inequality is not enough to prove that $B_x=n$.

What is missing from the steps above and what will save the day in the end is the fact that $x$ is an integer.

To wit, assume that $B_x=n+1$. Then, $\frac12(\sqrt{1+8x}-1)>n$ hence $x>\frac12n(n+1)$. Since $x$ and $\frac12n(n+1)$ are both integers, $$ x\ge\textstyle{\frac12}n(n+1)+1. $$ The inequality $\sqrt{2x}+\frac12<n+1$ from which we started reads $$ \sqrt{n^2+n+2}<n+\textstyle{\frac12}, $$ which is impossible. Hence $B_x=n$ and $B_x=A_x$.

Added in note It is an interesting exercise to spot the point where the proof above goes astray for $x=0$. (Hint: as is often the case, almost right from the start.)