Hello, sbankica!

Consider , the number of 7-digit numbers that contain "666".Find a recurrence relation for ,

where is the number of n-digit sequences

(each digit taken from {0, 1, 2, ... 9})

that contain “666” somewhere in the sequence.

One of them is: .

Write it like this: .

There are 6 spaces ( spaces) in which to insert the eighth digit.

. . and there are 10 choices for the eighth digit.

Hence, there are: ways to change into an 8-digit number.

That is: .

In general: .

Edit: I suspect that there is some duplication in my solution,

. . . .but I'm unable to eliminate it.

.