# Need help with proof

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

Edit: Sorry, forgot to mention: x is an integer.

-
The parentheses on your left hand side were unbalanced, so I don't know if this is what you meant to write; if it is not, then feel free to correct it. –  Arturo Magidin Jul 2 '11 at 7:27
Have you noticed yet that $$\frac{\sqrt{1+8x}-1}{2} = \sqrt{\frac{1+8x}{4}} - \frac{1}{2} = \sqrt{\frac{1}{2} + 2x} - \frac{1}{2}\ ?$$ –  Arturo Magidin Jul 2 '11 at 7:29
@Arturo: I think that you meant $\sqrt{\frac{1}{4} + 2x} - \frac{1}{2}$. –  Brian M. Scott Jul 2 '11 at 7:39
For $x=17/16$ you get $\lfloor 1.9577\ldots \rfloor =1$ but $\lceil 1.0411\ldots \rceil =2$ –  Henry Jul 2 '11 at 8:10
@Brian: Yes, of course. Thank you. –  Arturo Magidin Jul 2 '11 at 15:46

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