This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

0 01 01011 0101101011011 0101101011011010110101101101011011 etc.

Each string is formed from the previous string by substituting '01' for '0'

and '011' for '1' simultaneously at each occurance.

Notice that each string is an initial substring of the previous string so

that we may consider them all as initial substrings of an infinite string.

The puzzle then is, given n, determine if the nth digit is 0 or 1 without

having to construct all the previous digits. That is, give a non-recursive

formula for the nth digit.

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)

Continue to: