Q:

For any integer n >=1, let Fn be the number of aa-free strings of length n. Determine F1, F2, F3

Question: We consider strings of characters, where each character is an
element of {a; b; c}. Such a string is called aa-free, if it does not contain two consecutive a's. For any integer n > = 1, let Fn be the number of aa-free strings of length n.

Determine F1, F2, and F3.
Prove that for every integer n >= 1,

Fn = (1/2 + 1/sqrt(3)) * (1 + sqrt(3))^n + (1/2 - 1/(sqrt(3)) * (1 - sqrt(3))^n
Hint: What are the solutions of the equation x^2 = 2x + 2? Using these solutions will simplify the proof.
I'm not sure how to proceed with this question. Like do I take values of n and come up with the solution? I'm also not sure how using the equation in the hint is supposed to help me prove the equation is satisfied for every n>=1 value.

A:

Of course it is easy to verify that $F_1=3$, $F_2=8$, and $F_3=22$. I would break up the problem by looking at a string of length $n$ as a string of length $n-1$ concatenated with one character on the right.
I will define $G_n$ to be the number of aa-free strings of length $n$ ending with a, and $H_n$ to be the number of aa-free strings of length $n$ not ending with a. Then $F_n=G_n+H_n$, $G_n=H_{n-1}$, and $H_n=2F_{n-1}$. This is because for $G_n$, we are forced to end with a, while the first part must not end with a; and for $H_n$, we are forced to end with b or c (2 choices), but can use any aa-free string before that. 
Substituting $H_{n-1}$ for $G_n$ and $2F_{n-1}$ for $H_n$ in the first equation gives $F_n=2F_{n-2}+2F_{n-1}$. The solution to this linear recurrence equation can be written as
$$F_n=Ar_1^n+Br_2^n$$
with $r_1$ and $r_2$ being the solutions of the equation $x^2=2x+2$. Plugging these in for $r_1$ and $r_2$ and using the values of $F_1$ and $F_2$ to solve for $A$ and $B$ gives the desired result.

