Return-Path: <theorynt@FLASH.USC.EDU>
Approved-By:  Doug Ierardi <theorynt@FLASH.USC.EDU>
Newsgroups:   bit.listserv.theory-c
Date:         Tue, 23 Aug 1994 00:50:48 PDT
Reply-To: Hermann Stamm-Wilbrandt <hermann@uran.informatik.uni-bonn.de>
Sender: Theory-C - TheoryNet General Discussions <THEORY-C%NDSUVM1.BITNET@mitvma.mit.edu>
From: Hermann Stamm-Wilbrandt <hermann@uran.informatik.uni-bonn.de>
Subject:      Fibonacci numbers and the alphabet {0,1,2}^*
Comments: To: theory-c@vm1.nodak.edu
To: Local Distribution <theory-c-mit@THEORY.LCS.MIT.EDU>



Hello!

Many relations are known about fibonacci numbers, but can the
following be found somewhere in the literature, too?

  L_k = { w \in {0,1,2}^k | \not\exist u,v \in {0,1,2}^*: w=u10v }

        ( L_k is {0,1,2}^k with "forbidden subsequence 10" )

Theorem: |L_k| = f_{2k+2}  ( f_1=f_2=1 f_{i+1}=f_i+f_{i-1}, f_i ith fibonacci nu
mber )


Example: k=3; forbidden words 100 101 102 010 110 210 => 3^3-6=21=f_8=f_{2*3+2}

Proof:  the following FSA accepts L_k in states S and S1, starting state is S.

                              1
            +----- +---+ ----------> +----+      0       +-----+ -------+
        0,2 |      | S |             | S1 | -----------> | S10 |        | 0,1,2
            +----> +---+ <---------- +----+              +-----+ <------+
                              2       ^  |
                                      |  | 1
                                      +--+


Now the number of words from {0,1,2}^i in the different states is given by

    S(0)   = 1    S(i+1)   = S1(i) + 2*S(i)
    S1(0)  = 0    S1(i+1)  = S1(i) + S(i)
    S10(0) = 0    S10(i+1) = S1(i) + 3*S10(i)


Claim: S(i) = f_{2i+1}, S1(i) = f_{2i}
       ( ==> |L_k| = S(k) + S1(k) = f_{2k+1} + f_{2k} = f_{2k+2} )

    S(0) = 1 = f_{2*0+1}   S1(0) = 0 = f_{2*0}    (f_0=f_2-f_1=1-1=0)

    S(i+1) = S1(i)+2*S(i) = f_{2i} + 2*f_{2i+1}
                          = (f_{2i} + f_{2i+1}) + f_{2i+1}
                          = f_{2i+2} + f_{2i+1}
                          = f_{2i+3}
                          = f_{2(i+1)+1}

    S1(i+1) = S1(i)+S(i)  = f_{2i} + f_{2i+1}
                          = f_{2i+2}
                          = f_{2(i+1)}


Any comments and literature pointers welcome ....

Thanks,

   Hermann.