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
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 $\displaystyle S_n$ be the number of stings of length n not containing the pattern 666.
Now it is clear that WHY?
How many of those 999 in $\displaystyle S_3$ end in 66?
So how many are there is $\displaystyle S_4$?
Now find a general pattern.