wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Zeroes in binary expansion of sqrt(2)
        
(Message started by: Aryabhatta on Sep 1^st, 2009, 9:19am)

Title: Zeroes in binary expansion of sqrt(2)
Post by Aryabhatta on Sep 1^st, 2009, 9:19am

Consider the binary expansion of sqrt(2)

1.01101010000010011110011001100111111...

Suppose a sequence of k zeroes or more first appears at such a position such that there are a_k digits after the decimal (binary?) point upto that position.

For instance a₁ = 0
a₄ = 7
a₅ = 7

etc.

If a sequence of k zeroes or more does not appear at all (which is probably not true) define a_k = k.

Show that for all k,

a_k >= k-1

Title: Re: Zeroes in binary expansion of sqrt(2)
Post by Eigenray on Sep 3^rd, 2009, 3:47pm

[hideb]Say http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 = r + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif, with http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif > 0. Letting f(x) = x² - 2, we have
0 = f(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2) = f(r) + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif f'(t),
for some t in [r, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2]. But then
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif= |f(r)| / f'(t) = |f(r)|/(2t) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif |f(r)|/2^3/2.
But if r = m/2^a, with m an integer, then
|f(r)| = | r² - 2 | = | (m² - 2^2a+1 ) / 2^2a | http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1/2^2a,
so http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1/2^2a+3/2 > 1/2^2a+2.
Therefore a string of (a+2) 0s cannot appear beginning a digits after the decimal point: if k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif a+2, then a_k > a; that is, a_k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif k-1.[/hideb]