A word of length $n$ is a sequence of letters obtained from some set.
For this problem, consider a word of length $n$ whose letters come from the set $\{0,1\}$. Let $w(n)$ denote the number of such words without adjacent zeros. For example $w(2)=3$ since the only valid words are $01, 10, 11$.
I have found that for $n\geq 3$ $$w(n)=w(n-1)+w(n-2)$$ where $w(1)=2$ and $w(2)=3$.
I would like to prove the recurrence relation combinatorially, but I have no idea how to begin. Any help is appreciated.
Hint. Any such word ends with a $1$ or a $10$.