Count the number of times that the number '13' appears at least once in an n digit number

Solution 1:

If your ultimate goal is to count the number of length-$n$ strings that contain 13 at least once, counting the number of repeats is not going to help; it is strictly harder.

Instead, let $a_n$ be the number of length-$n$ strings that don't contain 13 at all. There is a recurrence $$a_n = 10 a_{n-1} - a_{n-2}$$ justified as follows: to any of the $a_{n-1}$ strings of length $n-1$ with no 13, we may append any of $10$ digits, except for $a_{n-2}$ cases in which the result is a string ending in 13 (but with no other occurrences of 13 in it).

Together with the base cases $a_1 = 10$ and $a_2 = 99$, this gives a shifted version of the OEIS sequence A004189. From there, or from standard tricks for linear recurrences, we can find $$a_n = \frac{(5 + 2\sqrt 6)^{n+1} - (5-2\sqrt 6)^{n+1}}{4 \sqrt 6}.$$

The number of length-$n$ strings that do contain 13 at least once, then, is given by $10^n - a_n$.

If you still want to count the number of "repeat occurrences of 13" (that is, the number of times over all length-$n$ strings that 13 appears in a string not for the first time), then this can be done in terms of $a_n$; it won't help us find $a_n$.

The total number of 13's that appear in these strings is $(n-1)10^{n-2}$: there are $n-1$ places we could put a 13, and $10^{n-2}$ places to choose all the other digits. This counts a string with $k$ occurrences of 13 $k$ times; we want to count it $k-1$ times. So we may subtract the previously found $10^n - a_n$ to get the formula $$ (n-1)10^{n-2} - 10^n + a_n. $$