==> series/series.19.s <== Let G equal the limit string generated by the above process and define the string F by F[0] = "0", F[n] = "1" if n = floor(phi*m) for some positive integer m, F[n] = "0" if n = floor(phi^2*m) for some positive integer m, where floor(x) is the greatest integer =< x and phi = (1 + \/5)/2; I claim that F = G. I will try to motivate my solution. Let g[0]="0" and define g[n+1] to be the string that results from replacing "0" in g[n] with "01" and "1" with "011"; furthermore, let s(n) and t(n) be the number of "0"'s and "1"'s in g[n], respectively. Note that we have the following recursive formulas : s(n+1) = s(n) + t(n) and t(n+1) = s(n) + 2t(n). I claim that s(n) = Fib(2n-1) and t(n) = Fib(2n), where Fib(m) is the mth Fibonacci number (defined by Fib(-1) = 1, Fib(0) = 0, Fib(n+1) = Fib(n) + Fib(n-1) for n>=0); this is easily established by induction. Now noting that Fib(2n)/Fib(2n-1) -> phi as n -> infinity, we see that if the density of the "0"'s and "1"'s exists, they must be be 1/phi^2 and 1/phi, respectively. What is the simplest generating sequence which has this property? Answer: the one given above. Proof: We start with Beatty's Theorem: if a and b are positive irrational numbers such that 1/a + 1/b = 1, then every positive integer has a representation of the form floor(am) or floor(bm) (m a positive integer), and this representation is unique. This shows that F is well-defined. I now claim that Lemma: If S(n) and T(n) (yes, two more functions; apparently today's the day that functions have their picnic) represent the number of "0"'s and "1"'s in the initial string of F of length n, then S(n) = ceil(n/phi^2) and T(n) = floor(n/phi) (ceil(x) is the smallest integer >= x). Proof of lemma: using the identity phi^2 = phi + 1 we see that S(n) + T(n) = n, hence for a given n either S(n) = S(n-1) + 1 or T(n) = T(n-1) + 1. Now note that if F[n-1]="1" ==> n-1 = floor(phi*m) for some positive integer m and since phi*m-1 < floor(phi*m) < phi*m ==> m-1/phi < (n-1)/phi < m ==> T(n) = T(n-1) + 1. To finish, note that if F[n-1]="0" ==> n-1 = floor(phi^2*m) for some positive integer m and since phi^2*m-1 < floor(phi^2*m) < phi^2*m ==> m-1/phi^2 < (n-1)/phi^2 < m ==> S(n) = S(n-1) + 1. Q.E.D. I will now show that F is invariant under the operation of replacing "0" with "01" and "1" with "011"; it will then follow that F=G. Note that this is equivalent to showing that F[2S(n) + 3T(n)] = "0", F[2S(n) + 3T(n) + 1] = "1", and that if n = [phi*m] for some positive integer m, then F[2S(n) + 3T(n) + 2] = "1". One could waste hours trying to prove some fiendish identities; watch how I sidestep this trap. For the first part, note that by the above lemma F[2S(n) + 3T(n)] = F[2*ceil(n/phi^2) + 3*floor(n/phi)] = F[2n + floor(n/phi)] = F[2n + floor(n*phi-n)] = F[floor(phi*n+n)] = F[floor(phi^2*n)] ==> F[2S(n) + 3T(n)] = "0". For the second, it is easy to see that since phi^2>2, if F[m]="0" ==> F[m]="1" hence the first part implies the second part. Finally, note that if n = [phi*m] for some positive integer m, then F[2S(n) + 3T(n) + 3] = F[2S(n+1) + 3T(n+1)] = "0", hence by the same reasoning as above F[2S(n) + 3T(n) + 2] = "1". Q.E.D. -- clong@remus.rutgers.edu (Chris Long)