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.

  • $\begingroup$ 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. $\endgroup$ – Arturo Magidin Jul 2 '11 at 7:27
  • 5
    $\begingroup$ 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}\ ?$$ $\endgroup$ – Arturo Magidin Jul 2 '11 at 7:29
  • 3
    $\begingroup$ @Arturo: I think that you meant $\sqrt{\frac{1}{4} + 2x} - \frac{1}{2}$. $\endgroup$ – Brian M. Scott Jul 2 '11 at 7:39
  • 1
    $\begingroup$ For $x=17/16$ you get $\lfloor 1.9577\ldots \rfloor =1$ but $\lceil 1.0411\ldots \rceil =2$ $\endgroup$ – Henry Jul 2 '11 at 8:10
  • $\begingroup$ @Brian: Yes, of course. Thank you. $\endgroup$ – 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.)


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.