Find a recurrence relation for an, n>=0 where an is the number of n-digit sequences (each digit taken from {0, 1, 2, . . . , 9}) that contain “666” somewhere in the sequence.
Find a recurrence relation for an, n>=0 where an is the number of n-digit sequences (each digit taken from {0, 1, 2, . . . , 9}) that contain “666” somewhere in the sequence.
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.
.
Let b(n) be the number of n-digit sequence which contains no 666
anywhere in the sequence.
Obviously .
Divide b(n) into two classes:
Class A: s(n) be the number of sequence such that the n-th digit is not 6.
Class B: t(n) be the number of sequence such that the n-th digit is 6.
Then b(n)=s(n)+t(n),
To find b(n+1), we need to find s(n+1) and t(n+1):
It is very easy to (see)verify that, we have the following recursive definition:
s(n+1)=9b(n);
t(n+1)=s(n)+s(n-1);
And
s(1)=9,t(1)=1,b(1)=10;
s(2)=90,t(2)=10,b(2)=100.