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

        riddles >> medium >> Find the limiting pattern
        
(Message started by: gkwal on Jul 16th, 2007, 9:21pm)
Title: Find the limiting pattern
Post by gkwal on Jul 16th, 2007, 9:21pm
Let S1=A, S2=ABB, S3=ABBAA, S4=ABBAAABBABB, S5=ABBAAABBABBABBAAABBAA, etc. be a sequence of strings such that Sn is formed from Sn-1 by replacing every A by ABB and every B by A. Find the limiting frequency of the pattern AAB among 3-letter patterns in Sn as n grows to infinity.
Title: Re: Find the limiting pattern
Post by Eigenray on Jul 18th, 2007, 1:30am
Let an, bn be the number of A's and B's in Sn.  We have

[hide]an = an-1 + bn-1 = an-1 + 2an-2,

and this recurrence has solutions of the form

an = c*2n + d*(-1)n.

It follows from this that an ~ bn ~ c*2n as n goes to infinity.

Each AAB in Sn corresponds to a BA in Sn-1, and the BA's in Sn-1 correspond to the A's in Sn-2, except for the last A when Sn-2 ends in an A (when n is odd).  So the ratio is

(an-2 - (1-(-1)n)/2)/(an+bn) ~ c*2n-2 / (c*2n + c*2n) = 1/8.[/hide]


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board