Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
5  
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
2  
@Arturo: I think that you meant $\sqrt{\frac{1}{4} + 2x} - \frac{1}{2}$. –  Brian M. Scott Jul 2 '11 at 7:39
1  
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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