Recurrence relation

• Apr 23rd 2011, 10:52 PM
Oiler
Recurrence relation
Hi,

how can I find the recurrence relation and its initial conditions for the number of decimal strings of length n that do not contain the string 666. Thanks
• Apr 24th 2011, 04:12 AM
Plato
Quote:

Originally Posted by Oiler
find the recurrence relation and its initial conditions for the number of decimal strings of length n that do not contain the string 666.

Let $S_n$ be the number of stings of length n not containing the pattern 666.
Now it is clear that http://quicklatex.com/cache3/ql_a0ab...2bc70c6_l3.png WHY?
How many of those 999 in $S_3$ end in 66?
So how many are there is $S_4$?
Now find a general pattern.