Proof of patterns in Fibonacci words

Question

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.

Answer 1

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