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.

Printable View

- Nov 25th 2009, 08:56 PMsbankicafinding recurrence relation - question #2
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.

- Nov 26th 2009, 05:26 AMSoroban
Hello, sbankica!

Quote:

Find a recurrence relation for $\displaystyle a_n,\:n \geq 0$,

where $\displaystyle a_n$ 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: .$\displaystyle N \:=\:ab666cd$

Write it like this: .$\displaystyle \_\:a\:\_\:b\:\_\:6\,6\,6\:\_\:c\:\_\:d\:\_$

There are 6 spaces ($\displaystyle n-1$ spaces) in which to insert the eighth digit.

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

Hence, there are: $\displaystyle (10)(6)$ ways to change $\displaystyle N$ into an 8-digit number.

That is: .$\displaystyle a_8 \;=\;(10)(6)a_7$

In general: .$\displaystyle a_n \;=\;10(n-1)a_{n-1}$

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

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

. - Nov 26th 2009, 06:45 AMShanks
The above solution is obviously wrong!

This problem is very complicated! - Nov 26th 2009, 08:19 AMShanks
Let b(n) be the number of n-digit sequence which contains no 666

anywhere in the sequence.

Obviously $\displaystyle a(n)=10^{n}-b(n)$.

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.