# 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.

• Couldn't you do an inclusion-exclusion count for one 13, two 13s, three 13s and so on up to having numbers with 11 instances of 13 in them? I would think that would be how I'd tackle it. – JB King Dec 4 '15 at 23:52

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).