Can I solve this recurrence using the Fast Fibonacci transform? 
Write a program to calculate the total number of strings that are made of exactly N characters. None of the strings can have "13" as a substring. The strings may contain any integer from "0-9", repeated any number of times.

From above question I derived a recursive equation which gives total "13" s as follow:
$$F_{n} = 10F_{n-1} + 10^{n-2} - F_{n-2}$$
I am trying to solve the problem using Fast Fibonacci Transform with O(logn) time complexity as described in this link.
Taking reference to this post I tried to convert the obtained recursive equation into matrix recursive form:
I need to find A such that:
$$\begin{bmatrix} F_n \\\ F_{n-1} \end{bmatrix} = A \begin{bmatrix} F_{n-1} \\\ F_{n-2} \end{bmatrix}$$
But because of the presence of 10n-2 I am not getting the constant.
My $A$ looks like the following:
$$ A = \begin{bmatrix} 10 & -10^{n-2} \\\ 1 & 0 \end{bmatrix}$$
Thus matrix $A$ is not constant.
What should I do in this case?
Please shed some light
 A: The removal of the exponential term may be done by finding a particular solution to the recurrence. Letting $F_n=C\times10^n$, one has
$$C\times10^n=(C+0.01-0.01C)10^n$$
$$C=1.01C+0.01$$
$$C=-1$$
and thus we may consider $F_n=G_n-10^n$ to get
$$G_n=10G_{n-1}-G_{n-2}$$
$$\begin{bmatrix}G_n\\G_{n-1}\end{bmatrix}=\begin{bmatrix}10&-1\\1&0\end{bmatrix}\begin{bmatrix}G_{n-1}\\G_{n-2}\end{bmatrix}$$
$$\begin{bmatrix}G_{n+1}\\G_n\end{bmatrix}=\begin{bmatrix}10&-1\\1&0\end{bmatrix}^n\begin{bmatrix}G_1\\G_0\end{bmatrix}$$
and in terms of the original sequence,
$$\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}=\begin{bmatrix}10&-1\\1&0\end{bmatrix}^n\begin{bmatrix}F_1+10\\F_0+1\end{bmatrix}-10^n\begin{bmatrix}10\\1\end{bmatrix}$$
A: One solution is to add a dimension, and write
$$
\pmatrix{F_n\\F_{n-1}\\1} = 
\pmatrix
{10 & -1 & 10^{n-2}
\\
1 & 0 & 0
\\
0 & 0 & 1
}\pmatrix{F_{n-1}\\F_{n-2}\\1}
$$
Now at least you have a matrix multiplication. But as you'll surely note, that $10^{n-2}$ term isn't a constant. But you can fix that with
$$
\pmatrix{F_n\\F_{n-1}\\10^{n-1}} = 
\pmatrix
{10 & -1 & 10
\\
1 & 0 & 0
\\
0 & 0 & 10
}\pmatrix{F_{n-1}\\F_{n-2}\\10^{n-2}}
$$
I can't say whether this'll help you or not, but it's at least a way to express the recurrence as a matrix multiplication.
