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
Best Answer
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.