Conference rusure::math

706.0. "Two (or so) series/limit problems" by CLT::GILBERT (eager like a child) Sat May 16 1987 20:42

Here are a few interesting problems from Philippe Flajolet.

I)  What is happens as (x->1) to the series
    T(x)=1-x-x^2+x^3-x^4+x^5+x^6-x^7-x^8+x^9+x^10-x^11+...
    where the coefficient of x_n is t(n)=+1 if n, written in binary has
    an even number of 1-bits and t(n)=-1 otherwise.

For instance, 19=(16+2+1)=(10011) in binary, so that t(19)=-1.
The sequence t(n) is known as the Thue-Morse sequence in combinatorics

Question is: What is the growth [?? "shrinkage" may be more appropriate
here :-) --N.E.] rate of T(x) as x->1? Compare
with (1-x)^-lg(1-x) where lg=log base 2.
 
[ Hint: there is a trick involved.  Noam Elkies notes that the trick "seems
  to be a favorite of the Putnam exam committee -- it appeared in various
  disguises in at least three Putnam problems within the past two years".
  Noam asks: What about the behavior of sum(x^n*t(3n),n,0,inf) as x->1? ]

 
II) If you compute the infinite product:
    product (n+1)^t(n), for n>=0
modifying it slightly in order for it to make sense, e.g. as:

   2  5.8        9.12              (4p+1)(4p+4)
P= - (---)^t(1) (---- )^t(2) ... (--------------)^t(p) ...
   3  6.7        10.11             (4p+2)(4p+3)

you find with 2000 terms:
ie p<=2000 or n<=2000 ?]
    P=~=.70710675913....
    P^2=~=.49999996881952
Any explanation?
 
[ The solution is both elegant and elementary ]


In the analysis of a probabilistic estimation algorithm I encountered P'
    P'=(2/3) product p>=1 ((4p+1)(4p+2)/(4p(4p+3))^t(p)
for which I did not find a closed form. Any hints?