how to write a recursive definition 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.
Show that the algorithms $(2n+1)$ are recursive.                                                                                                                                                                                                                                           Can someone help to get the result of this problem? Thanks