The proof I am working toward achieving is as follows:
I know this can be proven using induction, and in doing so, I will need to:
- show when n = 2, F₂ = G₀; when n = 3, F₃ = G₁; if $F_{n -1} = G_{n - 3}$, then $F_n = G_{n - 2}$ for any $n > 2$
- $G_{n - 3} = F_{n - 1}$; $G_{n - 4} = F_{n - 2}$; $G_{n - 2} = G_{n - 3} + G_{n - 4}$; $F_{n - 1} + F_{n - 2} = F_n$
- $F_n = G_{n - 2}$ for all $n > 2$
Let's just show that combinatorically,
Let $G_n$ be that number, let's look on a word that is legal first letter: - if it's an 'a' then the next letter must be 'b' and the remainder is a legal word with $n-2$ letters - $G_{n-2}$ - if it's a 'b' then the remainder is a legal word with length $n-1$ - $G_{n-1}$
Therefore $$G_n = G_{n-1} + G_{n-2}$$
With initial conditions: $G_0 = 1$ - the empty word is legal of length zero, and $G_1 = 2$, since all the words of length 2 are legal. Since $G_0 = F_2$ and $G_1 = F_3$ we get exactly what we want.