Recursion for amount of $n$-digit numbers which don't have blocks of the form $000,111,222,\dots,999$

40 Views Asked by At

Let $a_n$ be the amount of $n$-digit numbers which don't have blocks of the form $000,111,222,\dots,999$.

I want to find a recursion for $a_n$.

$a_n=10a_{n-1}-???$

I know I have to substract the amout of new 'invalid' numbers but I don't how to express them in terms of $a_{(.)}$