# How many natural numbers smaller than or equal to $10^{23}$ do not contain the pattern 13?

For my combinatorics course, I have to answer the following question:

How many natural numbers smaller than or equal to $10^{23}$ do not contain the pattern $13$? (We consider $0$ as a natural number).

I tried to solve this using a recurrence relation:

Call $f_n$ the amount of natural numbers smaller than or equal to $10^n$ that do not contain $13$.

I considered $2$ cases:

Case $1$: The last digit is not equal to $3$
We have $9$ options for chosing this last digit, so $9 \cdot f_{n - 1}$ combinations.

Case $2$: The last digit is equal to $3$
We have $9$ options for the second last digit. I don't know how to complete this step...

So by now, I know that the recurrence relation is of this form:

$f_{n} = 9 \cdot f_{n - 1} + ... + 1$. I added the 1 because $10^n$ is also one of the options.

I'm really stuck here, so could you please help me complete case 2 and find the recurrence relation? Or else correct me if there was something else in my computation so far that is not correct or could be done easier.

Forget numbers and think just in terms of strings of length $n$ over the alphabet $\{\mathtt 0,\mathtt 1,\mathtt 2,\mathtt 3,\mathtt 4,\mathtt 5,\mathtt6, \mathtt7,\mathtt 8,\mathtt 9\}$ that do not contain $\mathtt{13}$. Let the number of such strings be $a_n$.
We can make such a string by taking any such string of length $n-1$ and appending one of the $10$ digits -- except that if the shorter string ends with $\mathtt 1$, we have only $9$ options because we need to avoid $\mathtt 3$.
How many valid strings of length $n-1$ end with $\mathtt 1$? Evidently there must be $a_{n-2}$ of those, because any valid string of length $n-2$ can be legally followed by $\mathtt 1$.
Thus, $$a_n = 10a_{n-1} - a_{n-2}$$ leading to the Binet-like formula $$a_n = \frac{1+5/\sqrt{24}}2 (5+\sqrt{24})^n - \frac{5/\sqrt{24}-1}2 (5-\sqrt{24})^n = \left\lfloor \frac{1+5/\sqrt{24}}2 (5+\sqrt{24})^n \right\rfloor$$ and your answer is then $a_{23}+1$ (to account for $10^{23}$ too).