For $n\in\mathbb{N}$ we call a finite sequence $x_{1}x_{2}\ldots x_{n}$ a word if $x_{i}\in\{0,1\}$ for all $1\leq i\leq n$. We say that a word is allowed if it satisfies the following two conditions:
- The word starts with $1$ or $00$,
- Between two $1$'s there is an even number of $0$'s.
Examples of allowed words are $1001$ (length $4$), $00011$ (length $5$), $001110$ (length $6$) and $1000010$ (length $7$).
Now define $w_{n}$ to be the number of allowed words of length $n$. How do I prove that $$w_{n+2}\geq w_{n+1}+w_{n}?$$
EDIT: What I tried so far: Let $W_{n}$ be the set of allowed words of length $n$. Then it is not hard to see that $00W_{n}\subset W_{n+2}$ and $0W_{n+1}\subset W_{n+2}$. Similar constructions can be made by placing other symbols in front of the sets $W_{n}$ and $W_{n+1}$. However, I did not succeed to construct disjoint sets $xyW_{n}$ and $zW_{n+1}$ such that $xyW_{n}\subset W_{n+2}$ and $zW_{n+1}\subset W_{n+2}$ for $x,y,z\in\{0,1\}$. If this is possible, it is not hard to finish the proof.
Hint:
Consider an allowed word of length $n+1$. If there was a $1$ in it appearing anywhere, transform this into a word of length $n+2$ by inserting a $1$ right after the first $1$ that appears. For example $000\color{blue}1001\mapsto 000\color{blue}1\color{red}{1}001$. Else, if no $1$'s appeared then insert a $1$ at the very end.
Meanwhile consider an allowed word of length $n$. If there was a $1$ in it, insert two zeroes right after the first $1$ that appears. For example $00\color{blue}100100\mapsto 00\color{blue}1\color{red}{00}00100$. If no $1$ appeared, then insert two $0$'s at the very end.
Prove that these operations will indeed result in another good word in every case and prove that the set of words formed by the first case are not repeated in the set of words formed by the second case.