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

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.

1. Determine F1, F2, and F3.
2. 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.

• The thing that's missing is that you're supposed to come up with a recurrence relation, an equation relating $F_n$ to $F_{n-1}$ and $F_{n-2}$ (and then you're supposed to know how to solve that kind of recurrence relation). Oct 10, 2018 at 23:11

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.