The Fibonacci sequence
is a well known and ubiquitous sequence of natural numbers.
You can find Fibonacci numbers everywhere starting from… your personal rabbit hutch…
Similarly, there exists a well known formal language,
The Fibonacci Language
containing all the words defined by the following word concatenation:
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'
... for i in range(1,N):
... print Fib(i)+'\n'
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 . The first two fibonacci words are of length . Fix and assume that does not contain ’00’ nor ‘111’ for every . Then does not contain '00', otherwise applying induction hypothesis it must be with and . Observe that the only Fibonacci word starting with 0 is because and every Fibonacci word has as a prefix. This imply hence , this is not possible since .
Now we consider substring '111'. If contains '111', applying induction hypothesis it must be one of two cases:
case 1: for and
This imply that there exists a Fibonacci word that ends with ’11’. Consider the shortest Fibonacci word ending with ’11’, assume this is , wlog . Then ends with ’11’ as well because is the suffix of . This is against the minimality of and leads to a contradiction.
case 2: for and
every Fibonacci word has as a prefix so this case is not possible.