Let Fibonacci words over the alphabet $\{0,1\}$ be recursively defined by $\omega_0=0$, $\omega_1=01$, and $\omega_n=\omega_{n-1}\omega_{n-2}$ for $n\geq{2}$. I am trying to show that the patterns $11$ and $000$ never occur in any Fibonacci words. I am not sure how to go about proving this because I need to show that NO words contain these patterns. I tried using induction but I was not sure how to show that the statement is true for the next Fibonacci number.


Hint: First prove two lemmas:

  1. All words (but $w_0$) start with $01$
  2. No word ends with $00$

They are both can be easily proven by induction.

The main statement immediately follows from them (also by induction).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.