-2
$\begingroup$

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.

$\endgroup$

closed as off-topic by Namaste, Leucippus, Xander Henderson, Chris Custer, Don Thousand Oct 11 '18 at 4:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Leucippus, Xander Henderson, Chris Custer, Don Thousand
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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). $\endgroup$ – Gerry Myerson Oct 10 '18 at 23:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much, this makes the approach clear to me $\endgroup$ – Toby Oct 13 '18 at 2:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.