Fibonacci’s words.

The Fibonacci sequence f_n = \left\{ \begin{array}{ll} 0 & \quad n = 1 \\ 1 & \quad n = 2 \\ f_{n-1} + f_{n-2} & \quad n \geq 3 \\ \end{array} \right.
is a well known and ubiquitous sequence of natural numbers.

You can find Fibonacci numbers everywhere starting from… your personal rabbit hutch…

rabbithutch

Similarly, there exists a well known formal language,

The Fibonacci Language

containing all the words defined by the following word concatenation:

F_n = \left\{ \begin{array}{ll} ' 0 ' & \quad n = 1 \\ ' 1 ' & \quad n = 2 \\ F_{n-1} F_{n-2} & \quad n \geq 3 \\ \end{array} \right.

We speak out loud the first ten Fibonacci words with the following python code:

>>> def Fib(n):
...   if n < 1:
...      return 'illegal arg'
...   elif n == 1:
...      return '0'
...   elif n == 2:
...      return '1'
...   elif n > 3:
...      f = Fib(n-1)+Fib(n-2)
...      return f


>>> def SpeakOutLoudFibo(N):
...  if N < 1:
...     print 'illegal arg'
...   else:
...      for i in range(1,N):
...        print Fib(i)+'\n'
...


>>> SpeakOutLoudFibo(11)
0

1

10

101

10110

10110101

1011010110110

101101011011010110101

1011010110110101101011011010110110

1011010110110101101011011010110110101101011011010110101

Then we look at the first Fibonacci words and see the following:

Claim. The fibonacci language contains no words having ’00’ nor ‘111’ as substrings.
Proof. We proceed by induction on n. The first two fibonacci words are of length 1. Fix n and assume that F_m does not contain ’00’ nor ‘111’ for every m < n. Then F_n does not contain '00', otherwise applying induction hypothesis it must be F_n = F_{n-1}F_{n-2} = x00y with F_{n-1}=x0 and F_{n-2}=0y. Observe that the only Fibonacci word starting with 0 is F_1 because F_2=1 and every Fibonacci word has F_1 as a prefix. This imply F_{n-2}=0=F_{1} hence n = 3, this is not possible since F_3 = 10.
Now we consider substring '111'. If F_n contains '111', applying induction hypothesis it must be one of two cases:
case 1: F_n = x11\cdot 1y for F_{n-1} = x11 and F_{n-2} = 1y
    This imply that there exists a Fibonacci word that ends with ’11’. Consider the shortest Fibonacci word ending with ’11’, assume this is F_s, wlog s\geq 3. Then F_{s-2} ends with ’11’ as well because is the suffix of F_s. This is against the minimality of |F_s| and leads to a contradiction.
case 2: F_n = x1\cdot 11y for F_{n-1} = x1 and F_{n-2} = 11y
    every Fibonacci word has F_3 = 10 as a prefix so this case is not possible.
Q.E.D.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s