so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to write out every combination from head but i am pretty sure i didnt have to do that. i got s(0)=1,s(1)=3,s(2)=8,s(3)=22
from what i tried to do i got s(n)=2(n-1)+2(n-2) but not sure if i am right.
can someone explain how to do this kind of problems.
A more complete answer may be in order. From my comment,
$$s(n) = s_a(n) + s_b(n) + s_c(n)$$
Now look at what happens when you add a letter to the end. Adding a c to the end of any string with no "aa"s is still a string with no "aa"s. So...
$$s_c(n+1) = s(n)$$
Similarly for adding a b to the end.
$$s_b(n+1) = s(n)$$
Now adding an a to the end only counts if the previous string did not end in a.
$$s_a(n+1) = s_b(n) + s_c(n)$$
And so we have, by adding all the pieces:
$$s(n+1) = s_a(n+1) + s_b(n+1) + s_c(n+1) = 2 s(n) + s_b(n) + s_c(n) = 2 s(n) + 2 s(n-1)$$
where that last equality uses the formulas for $s_b$ and $s_c$ derived earlier.