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.

Thanks in advance!!!

  • 1
    $\begingroup$ 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. $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.