<s>[INST] How many five-digit numbers do not have three consecutive digits the same? How many five-digit numbers do not have three consecutive digits the same? Also, the initial digits might be $0$, but I'm not sure how that changes the answer. 
This is the formula I've come up with for solving this problem. 
Total number of numbers - $A - B - C + A \cap B + B \cap C + A \cap C - A \cap B \cap C$ 
$$10^5 - (10^3 \cdot 3) + (10^2 \cdot 2) - 10$$
So I have
set $A$, positions 1 2 3 are filled;
set $B$, positions 2 3 4 are filled;
set $C$, positions 3 4 5 are filled;
so each set will have $10 \cdot 10 \cdot 10$ subsets of numbers that have $3$ consecutive numbers. 
I know that their should be double counting because having consecutive numbers in positions 1 2 3 4 and 2 3 4 5 should be added back, and consecutive numbers 1 2 3 4 5 will need to be subtracted.
So, I get 
$$10^5 - (10^3 \cdot 3) + (10^2 \cdot 2) - 10 = 100000 - 3000 + 200 - 10 
= 97190$$ 
However, this is not the correct answer. What is the correct procedure to solve this problem? Or what way am I to look at counting up the sets?
Thanks
 [/INST] This problem can be broken down into two cases-


*

*When no consecutive digits are same

*When two consecutive digits are same


The answer would be the sum of the number of ways of the two indvidual cases.

If f(n) be the answer to the above problem having n number of digits. Then, 
f(n) = 9*(f(n-1)+f(n-2))
 The equation can be represented in matrix from as,
\begin{equation*}
\begin{bmatrix}
f(n) \\
f(n-1) \\
\end{bmatrix} =
\begin{bmatrix}
9 & 9 \\
1 & 0 \\
\end{bmatrix}*\begin{bmatrix}
f(n-1) \\
f(n-2) \\
\end{bmatrix}
\end{equation*}
Solving the recurrence, we get,
\begin{equation*}
\begin{bmatrix}
f(n) \\
f(n-1) \\
\end{bmatrix} =
\begin{bmatrix}
9 & 9 \\
1 & 0 \\
\end{bmatrix}^{n-2}*\begin{bmatrix}
f(2) \\
f(1) \\
\end{bmatrix}
\end{equation*}
Clearly, the base cases are f(1) = 10 and f(2) = 100.

This can now be solved using matrix exponentiation having computation complexity of (k3log(n)) where k=2 (size of the square matrix).
Now, considering the above asked question, plugging n=5 into the recurrence gives,
 
\begin{equation*}
\begin{bmatrix}
f(5) \\
f(4) \\
\end{bmatrix} =
\begin{bmatrix}
9 & 9 \\
1 & 0 \\
\end{bmatrix}^{3}*\begin{bmatrix}
100 \\
10 \\
\end{bmatrix}
\end{equation*}
i.e.,
\begin{equation*}
\begin{bmatrix}
f(5) \\
f(4) \\
\end{bmatrix} =
\begin{bmatrix}
891 & 810 \\
90 & 81 \\
\end{bmatrix}*\begin{bmatrix}
100 \\
10 \\
\end{bmatrix}
\end{equation*}
Therefore,
\begin{equation*} f(5)=891*100+810*10=97200\end{equation*}
</s>