How many 8-digit numbers do not contain a sub-string of 3 repeated digits?

Question

I am struggling quite a bit with the above question. I am unsure what formula to use to determine this, mainly due to the scale of the problem.

I tried 9x10x9x9x9x9x9X9, but I am unsure about this as a solution. My understanding is that the substring requirement would see 10,001,223 as a number with three repeated digits in a substring, but 10,100,100 does not contain a substring with three repeated digits.

I am very confused as to how to calculate this, any help determining a formula would be greatly appreciated.

Answer 1

(Fill in the gaps as needed. If you're stuck, show your work and explain where/why you are stuck.)

Hint: Let $f_{k, 1}$ be the number of $k-$ digit numbers that do not contain a substring of 3 repeated digits, and end with only 1 repeated digit.
Let $f_{k, 2}$ be the number of $k-$ digit numbers that do not contain a substring of 3 repeated digits, and end with only 2 repeated digits.

1. Prove the recurrence relation

$$ \begin{align} f_{k+1, 1 } & = 9 f_{k,1} + 9 f_{k,2} \\ f_{k+1, 2 } &= f_{k+1} \\ \end{align}$$

2. Determine suitable starting values.

3. Hence, find $f_{8,1} + f_{8,2}$.