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.

$\newcommand{\spec}{\operatorname{Spec}}\spec\sqrt2=\{\lfloor k\sqrt2\rfloor: k \ge 0\}$.

I have no idea of how I can prove the statement in the question.

Prove that $\spec\sqrt2$ contains infinitely many powers of $2$.

share|improve this question
2  
The most obvious place to start would be to enumerate the first few values of $\lfloor k \cdot \sqrt{2}\rfloor$ to get a feel for how it behaves. The next most obvious is to devise an algorithm for solving $\lfloor k \cdot \sqrt{2} \rfloor = 2^n$ for $k$. –  Hurkyl Oct 5 '12 at 21:10
1  
What a strange notation. Why $\mathrm{Spec} \sqrt{2}$? –  Alexander Shamov Oct 5 '12 at 21:12
    
@Alexander: Graham, Knuth, & Patashnik, Concrete Mathematics, refer to this sequence as the spectrum of $\sqrt2$. –  Brian M. Scott Oct 5 '12 at 21:12
    
As stated, this question is obviously true. Do you mean infinitely many integer powers of 2? –  Graphth Oct 5 '12 at 21:14
    
@Graphth: Of course. –  Brian M. Scott Oct 5 '12 at 21:15
show 7 more comments

1 Answer

up vote 2 down vote accepted

Let $k=\lceil 2^n\sqrt 2\rceil$. Then $2^n\sqrt 2<k<2^n\sqrt 2+1$. In fact we have either $2^n\sqrt 2<k<2^n\sqrt 2+\frac12$ or $2^n\sqrt 2+\frac12<k<2^n\sqrt 2+1$, depending on the ($n+1)$st binary digit of $\sqrt 2$ (which becomes the first digit of $2^n\sqrt 2$). Since $\sqrt 2$ is irrational, there are infinitely many $n$ (and correspondingly infinitely many $k$) such that $$2^n\sqrt 2<k<2^n\sqrt 2+\frac12$$ holds. Together with $k\sqrt 2 -1<\lfloor k\sqrt 2\rfloor <k\sqrt 2$ we find $$ 2^n\cdot 2-1 <\lfloor k\sqrt 2\rfloor <2^n\cdot 2+\frac{\sqrt 2}2,$$ hence $\lfloor k\sqrt 2\rfloor=2^{n+1}$.

share|improve this answer
    
Thanks for the answer, but I see a lot of unexplained things, which I don't seem to be able to comprehend :( . (n+1)st binary digit is the one counted from the left end, right? And, how does this bit influence the range of k like you posted? Infinitely many k? But k is a natural number, right? How would k take infinitely many values in between 2 real numbers differing by 1/2? –  learner Oct 5 '12 at 21:55
add comment

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.