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'

... 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 . 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.

**Q.E.D.**