# 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.

• Let's say you have a string of length n that does not contain "aa". Now say you want to make a string of length n+1 by appending an "a", "b", or "c" to the end. How do you know whether the new string also has no "aa" in it? Maybe if you broke up the counting to $s_a(n)$, $s_b(n)$, and $s_c(n)$ (where the index says we are counting the strings that end in a, b, or c respectively)? What is $s_a(n) + s_b(n) + s_c(n)$? These problems require thinking about "how" you recurse and giving it meaning. – ex0du5 Apr 2 '14 at 0:06
• Your figures for $s(0)$ through $s(3)$ are correct- you accept all strings except $aa, aaa, aab, aac, baa, caa$ – Ross Millikan Apr 2 '14 at 0:08

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