# 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…

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.