Recurrence relation for $n$ numbers in which no 3 consecutive digits are the same. I am stuck on trying to find (and solve) a recurrence relation to find all n-digit numbers in which no 3 consecutive digits are the same.  These numbers are in decimal expansion.  
Now I first imagine trying this for finding the number of n-digit numbers that don't have two consecutive digits.  If I am correct I have 10 choices for the first (we are in decimal expansion so 0 counts), then 9 choices for the second, 9 for the third and so on.  So we would have $10*9^{n-1}$ possible numbers.  This looks like it works for n = 2 as we would have 10 numbers {00,11,..,99} that are repeated.  I however wonder about 00, if that should be counted here, but for n > 2 I could have .001 etc.  I however figure that if .00 is not a valid number in decimal expansion then it also won't have to be removed.  Hence I have 90 numbers which work.  I can't quite see in to the n = 3 case though - it is this next digit (and so on) that boggle me.
Now I rigged up a recurrence relation that seems to work for the n = 1 and n = 2 case in the no consecutive 2 digit case.  It is:
$T(n) = 10^n - T(n-1) -1$  where T(0) = 0.  
$T(1) = 10^1 - T(0) - 1 = 9$  Note that 0 is not counted for n = 1 as it is .0 (hence the -1 included)
$T(2) = 10^2 - T(1) - 1 = 10^2 - (10^1 - T(0) - 1) - 1 = 100 - (10 - 0 - 1) - 1 = 90$
Since I don't know what T(3) is supposed to be I didn't bother putting it in.  If this Recurrence relation works, perhaps someone would have a combinatorial reason why it works?  
I however then am still stuck on the non 3 consecutive digit case and finding a recurrence relation for it.
Thanks for any thoughts,
Brian
 A: We can capture the essence of this problem by introducing two sequences, namely the sequence $a_n$ that counts the number of $n$-digit numbers that do not end in a repeated digit, starting with $a_2 = 9\times 10 -9 = 81$ and the number $b_n$ of $n$-digit numbers that end in two repeated digits, starting with $b_2 = 9.$
The problem definition translates straightforwardly into a pair of recurrences, namely
$$a_{n+1} = 9 a_n + 9 b_n
\quad \text{and} \quad
b_{n+1} = a_n.$$
We are interested in the quantity $$a_n+b_n.$$
By substitution we obtain
$$a_{n+1} = 9 a_n + 9 a_{n-1}$$
with characteristic equation
$$ x^2 = 9 x + 9$$
whose roots are
$$\rho_{1,2} = \frac{9}{2} \pm \frac{3}{2} \sqrt{13}.$$
Solving for $c_{1,2}$ in the system
$$ c_1\rho_1^2 + c_2\rho_2^2 = 81
\quad \text{and} \quad
c_1\rho_1^3 + c_2\rho_2^3 = 810$$
we obtain
$$ c_{1,2} = \pm \frac{3}{\sqrt{13}}$$
and hence
$$ a_n = 
\frac{3}{\sqrt{13}} \left( \frac{9}{2} + \frac{3}{2} \sqrt{13}\right)^n
- \frac{3}{\sqrt{13}} \left( \frac{9}{2} - \frac{3}{2} \sqrt{13}\right)^n.$$
Since $$a_n+b_n = a_n + a_{n-1} = \frac{1}{9} a_{n+1}$$
the final answer is
$$a_n + b_n = 
\frac{1}{3\sqrt{13}} \left( \frac{9}{2} + \frac{3}{2} \sqrt{13}\right)^{n+1}
- 
\frac{1}{3\sqrt{13}} \left( \frac{9}{2} - \frac{3}{2} \sqrt{13}\right)^{n+1}.$$
The first few values are
$$ 90, 891, 8829, 87480, 866781, 8588349, 85096170, 843160671, 8354311569.$$
This is sequence A057092 from the OEIS.
