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