3
$\begingroup$

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.

  • 0
    @Brian: Yes, of course. Thank you.2011-07-02

1 Answers 1

3

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} This translates as $ n^2-n+\textstyle{\frac14}\le2x that is, $a(n)\le\frac12(\sqrt{1+8x}-1) 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), $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 from which we started reads $ \sqrt{n^2+n+2} 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.)