My approach is to solve this problem using recursion. Let T(n) be the number of such n digit integers such that no 3 consecutive digits are 8.
Now there are a few cases:
Case 1: Last digit is not 8. So we are left with dealing with the remaining n-1 digits where the last digit can take any value except 8 i.e. the number of such numbers are 9T(n-1) since last digit can be anything but 8 and we have to apply recursion on the remaining n-1 digits.
Case 2: Last digit is 8. Now, here it gets a bit tricky. If the last digit is 8, then again for the 2nd last digit, we have two options, it is either 8 or it is not 8. If it is not 8, we have no problem , the number of cases will be 9T(n-2) since the last digit is 8, and the 2nd last is anything but 8, and we recurse on the previous n-2 digits in the integer.If the 2nd last digit is 8, then again, we must choose the 3rd last digit as not 8, so to avoid the subsequence 888. This can be done in 9T(n-3) ways as only the 3rd last digit should not be 8, and the remaining digits are already 8, so 9T(n-3), similarly recursing on the remaining n-3 digits.
So according to me number of such n digit integers such that no three digits are 8 can be solved by solving the recursion
T(n) = 9T(n-3)+9T(n-2)+9T(n-1)
The base cases are T(1) = 9, T(2)=90, T(3) = 899.
Is this solution correct? Thanks in advance.
Best Answer
You are completely right.
Just to check, it is fairly easy to count by cases that there are $18$ $4$-digit numbers that does contain $888$. Thus $T(4)=9000-18=8982$, which matches your recursive formula. Similarly, $T(5)$ should be $90000-261=89739$, which your formula also gives. We could check more with a program of course.
I also found the closed form formula for your recursion: $$ T(n) = 0.9015\cdot9.991^n - 0.0126 \cdot 0.949^n \cdot \cos(2.12\cdot n) - 0.0155\cdot 0.949^n\cdot \sin(2.12\cdot n) \\ = [0.9015\cdot9.991^n] $$ where $[\cdot]$ means rounded to nearest integer. (Exact algebraic values would involve roots of a cubic polynomial).