so the question is (to be solved with recurrence relations: How many numbers between 1 and 10,000,000 don't have the string 12 or 21?
So my solution: $a_n=10a_{n-1}-2a_{n-2}$. The $10a_{n-1}$ represents the number of strings of n length of digits from 0 to 9, and the $2a_{n-2}$ represent the strings of n-length with the 12 or 21 strings included.
Just wanted to know if my recursion is correct, if so, I'll be able to solve the rest.
Thanks in advance!
On
I see that André answered this while I was out putting $52$ miles on my bicycle, but let me suggest a very slightly different route to the same recurrence that occurred to me during my ride. I’ll use the same good terminology and the same definition of $a_n$, and I’ll let $c_n$ be the number of good strings of length $n$ that do not end in $1$ or $2$.
Suppose that $\sigma$ is a good string of length $n\ge 1$. No matter what the last digit of $\sigma$ is, there are at least $9$ digits that I can append to $\sigma$ to make a good string of length $n+1$, and if the last digit of $\sigma$ is not $1$ or $2$, I can append any of the $10$ digits. This accounts for all possible good strings of length $n+1$, so $a_{n+1}=9a_n+b_n$. How many of these do not end in $1$ or $2$? Precisely the ones obtained by appending one of the $8$ digits in $\{0,3,4,5,6,7,8,9\}$ to a good string of length $n$, of which there are $8a_n$. Thus, $b_{n+1}=8a_n$, so $b_n=8a_{n-1}$, and
$$a_{n+1}=9a_n+b_n=9a_n+8a_{n-1}\;.$$
Thus, we have
$$\left\{\begin{align*} &a_0=1\\ &a_1=10\\ &a_n=9a_{n-1}+8a_{n-2}\quad\text{for}\quad n\ge 2\;. \end{align*}\right.$$
That’s as far as you had to go, but I was curious about a closed form for $a_n$. By standard techniques one can discover that
$$a_n=\frac1{226}\left(\left(113+11\sqrt{113}\right)\left(\frac{9+\sqrt{113}}2\right)^n+\left(113-11\sqrt{113}\right)\left(\frac{9-\sqrt{113}}2\right)^n\right)\;.$$
Now $$\left|\frac{9-\sqrt{113}}2\right|<1\quad\text{and}\quad\left|\frac{113-11\sqrt{113}}{226}\right|<0.02\;,$$
and $a_n$ is always an integer, so for $n\ge 1$ $a_n$ is the integer closest to
$$\frac{113+11\sqrt{113}}{226}\left(\frac{9+\sqrt{113}}2\right)^n\;.\tag{1}$$
$(1)$ is approximately $(1.017396477611)(9.815072906367)^n$.
For $n=7$ this evaluates to approximately $8,927,809.995842$, which rounds to $8,927,810$, the correct value, so the approximation is pretty good.
We look at a slightly different problem, from which your question can be answered.
Call a digit string good if it does not have $12$ or $21$ in it. Let $a_n$ be the number of good strings of length $n$. Let $b_n$ be the number of good strings of length $n$ that end with a $1$ or a $2$, Then $a_n-b_n$ is the number of good strings of length $n$ that don't end with $1$ or $2$.
We have $$a_{n+1}=10(a_n-b_n) +9b_n.$$ For a good string of length $n+1$ is obtained by appending any digit to a good string that doesn't end with $1$ or $2$, or by appending any digit except the forbidden one to a good string that ends in $1$ or $2$.
We also have $$b_{n+1}=2(a_n-b_n) + b_n.$$ For we obtain a good string of length $n+1$ that ends in $1$ or $2$ by appending $1$ or $2$ to a string that doesn't end with either, or by taking a string that ends with $1$ (respectively, $2$) and adding a $1$ (respectively, $2$).
The two recurrences simplify to $$a_{n+1}=10a_n-b_n\qquad\text{ and}\qquad b_{n+1}=2a_n-b_n.$$ For calculational purposes, these are good enough. We do not really need a recurrence for the $a_i$ alone. However, your question perhaps asks about the $a_i$, so we eliminate the $b$'s.
One standard way to do this is to increment $n$ in the first recurrence, and obtain $$a_{n+2}=10a_{n+1}-b_{n+1}.$$ But $b_{n+1}=2a_n-b_n$, so $$a_{n+2}=10a_{n+1}-2a_n+b_n.$$ But $b_n=10a_n-a_{n+1}$, and therefore $$a_{n+2}=9a_{n+1}+8a_n.$$
Remark: It would have been better to have $b_n$ as above, and $c_n$ the number of strings that do not end in $1$ or $2$, and to forget about $a_n$ entirely for a while.