Number of strings of length $N$ made up of integer $0-9$ with repetition without $13$ as sub-string

Question

Calculate the total number of strings that are made of exactly $N$ characters, where $N$ is a positive integer. None of the strings can have "$13$" as a sub-string. The strings may contain any integer from $0-9$, repeated any number of times.

1. Is there any closed formula for calculating it?
2. Is there any recurrence relation for calculating it?

I want to understand how to approach this problem. I found a pattern (described below) but I cannot generalize it to find a formula or a recurrence relation.

Let $T(n)$ denote the required answer for the given $N$

For $N=1$, $T(n) = 10^1 = 10$

For $N=2$, $T(n) = 10^2 - 1(10^0) = 99$

For $N=3$, $T(n) = 10^3 - 2(10^1) + 0(10^{-1}) = 980$

For $N=4$, $T(n) = 10^4 - 3(10^2) + 1(10^0) = 9701$

But this pattern does not hold in next case:

For $N=5$, $T(n) \neq 10^5 - 4(10^3) + 2(10^1) - 0(10^{-1}) = 96020$

Answer 1

Call a string good if it satisfies your condition. Say $T_n$ is the number of good strings of length $n$. Now a good string may end up with a $1$ or any other digits from $\{0,2,3, \ldots ,9\}$. To create a good string of length $n+1$, we have two cases

Case 1: Good string of length $n$ ends with a $1$. Then for the $n+1^{\text{st}}$ digit, we can have anything except $3$. So the number of good strings of length $n+1$ that we can make from a good string of length $n$ (in this case) is $\color{blue}{9T_{n-1}}$ because $$\underbrace{x_1x_2 \ldots x_{n-1}}_{\text{ANY good string of length }n-1}\,\,\,\underbrace{\color{red}{1}}_{n^{\text{th}} \text{digit}}\,\,\,\,\,\underbrace{y}_{\text{any digit except }3}$$

Case 2: Good string of length $n$ ends with a digit from $\{0,2, \ldots ,9\}$. Then for the $n+1^{\text{st}}$ digit, we can have anything. So the number of good strings of length $n+1$ that we can make from a good string of length $n$ (in this case) is $\color{blue}{10(T_n-T_{n-1})}$ because $$\underbrace{x_1x_2 \ldots \color{red}{x_{n}}}_{\text{THOSE good string of length }n \text{ that have }x_n \neq 1}\,\,\,\,\,\,\,\underbrace{y}_{\text{any digit}}$$

Note: The number of good strings of length $n$ that DO NOT end with $1$ are the total number of good strings of length $n$ (i.e. $T_n$) minus those that do end with $1$ (which are $T_{n-1}$ as seen above)

Thus the total number of good strings pf length $n+1$ are $$T_{n+1}=9T_{n-1}+10(T_n-T_{n-1}) \implies \boxed{T_{n+1}=10T_n-T_{n-1}}$$ with $T_0=1$ and $T_1=10$.

In fact, you can solve this recurrence relation easily to get $$T_n=a(5+2\sqrt{6})^n+b(5-2\sqrt{6})^n.$$ Using the initial conditions, you can get $a$ and $b$.