recurrence formula for number of decimal numbers with some restrictions

Question

I ran into a Olympiad Question that so difficult,

if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find a recurrence for $a_n$. My note says:

$a_n=15a_{n-2}+7a_{n-1} $

I think this is not correct, anyone could help me to verify me and describe it for me?

Answer 1

So you want binary strings from an alphabet of $9$ digits that don't have $11,12$ or $21$.

Let's try to count these:

How many don't end in $0$ or $1$? For any sequence of length $n-1$ without the prohibited subsequence we can can add any of the $7$ digits $3,4,\dots 9$ at the end without having to worry. Thus there are $7a_{n-1}$.

How many sequences end in $1$? If a sequence ends in $1$ the digit before it is not $1$ or $2$. there are $7$ options for the digit before the $1$. And then we use the same argument as before to conlude there are $a_{n-2}$ possibilities for the sequence formed by all digits except the last two.

How many sequences end in $2$? There are two options, when the digit before the $2$ is not $2$ we can be sure it is not $1$ either, and we get $7a_{n-2}$.

Therefore there are $14a_{n-2}+7a_{n-1}$ desired sequences that do not end in $22$. So we must only add the number of sequences that end in $22$. But these are less than $a_{n-2}$. So I think it is wrong too.

---

I don't know if this helps but if $b_n$ is the number of desired sequences of length $n$ ending in $2$ we get:

$a_n=7a_{n-1}+14a_{n-2}+b_{n-1}$

$b_n=7a_{n-2}+b_{n-1}$

Although this does give us:

$a_n=7a_{n-1}+14_{n-2}+7(a_{n-3}+a_{n-4}+\dots a_{1})+b_2$

and since $b_2=8$ we get:

$a_n=7(a_{n-1}+a_{n-2}+\dots a_1)+8+7a_{n-2}$

Answer 2

$a_1 = 9 \\ a_2 = 81-3=78$

To assemble the numbers for $a_n$, we can take any of those for $a_{n-1}$ and add digits $3..9$ without problems ($7a_{n-1}$). To get the numbers that end in $2$ or $1$, we can take any numbers from $a_{n-2}$ and add digits $X1$ or $Y2$, where $X$ is $3..9$ and $Y$ is $2..9$ ($15a_{n-2}$). These two terms match the formula as given.

---

As pointed out in comments, this gives a case when there is an embedded $12$, from the case when adding "$22$" to a number that previously ended in $1$. This shows that the recurrence is incorrectly overcounting the possibilities.

I don't see any easy way to rescue the recurrence from there. A multiple-state counter works fine but is obviously more complicated than is looked for here.