How many 10-digit numbers do not have 3 consecutive digits the same.

Question

Define a Function $Q(n)$ that returns the number of n digit strings that do not contain 3 consecutive digits the same and starts with digit $k$.

Base Cases: $Q(0) = 0$, $Q(1) = 1$. since there is only one one digit string that starts with $k$ and no zero digit strings that start with $k$.

Then $Q(n) = 9Q(n - 2) + 9Q(n - 1)$

If the next digit is $k$ and we started in k, then we only have 9 choices for the next bit and then we can reapply $Q$ to a string of two less in size.

Similarly, if the next digit is not $k$ which can happen in 9 ways, then we again can reapply $Q$ on a string that is one less in size.

Since $Q$ works for a starting value $k$ and there are 9 different starting values, $G(n) = 9Q(n)$ returns the number of strings that do not contain 3 consecutive digits that are the same, with length n.

Now I am applying this on $n = 3$ and getting $810$ which is clearly not correct because the actual result should be $10^3 - 10 = 990$. Can someone tell me what things I am doing incorrectly here?

Answer 1

Your recursion formula can be justified as follows:

Every string of length $n$ with your desired property has either $1$ or $2$ equal digits at the end. If we remove these, we remain with a valid string. Therefore, we may build all of these strings, either by starting from a valid string of length $n-2$ and adding two repeated digits, distinct from the last, in one of $9$ ways, or by taking a valid string of length $n-1$ and adding a digit, distinct from the last, in one of $9$ ways. Therefore, $$Q(n)=9Q(n-2)+9Q(n-1).$$

As to your mistake. You correctly identify that this formula is useless without the first two base cases, which means that $Q(0)$ and $Q(1)$ must be calculated manually. However, consider the bolded part of the argument. This is actually false for $n=2$, since the string $kk$ can’t be built from a previous valid string, as the empty string doesn’t start with $k$. Instead, this holds only for $k\geq3$. This means that we must also consider the base case $$Q(2)=10,$$ and stipulate that our formula only works for $n\geq3$. We now get the correct result $Q(3)=99$.