-2

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.

Ѕᴀᴀᴅ
  • 34,263
Toby
  • 373
  • 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). – Gerry Myerson Oct 10 '18 at 23:11

1 Answers1

1

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.

HackerBoss
  • 472