Recursive relation to find a sequence $T_n$ I am working on defining an '$n$ digit' sequence $(T_n)$ where the string doesn't contain $99$: $929$ is okay but not $299$, and also $029$ is not okay as it will be considered a $2$-digit number and not $3$-digit (so it should basically not start with $0$).
So far I have got -

*

*$T_1 = 9$ cases (from $1$ to $9$)

*$T_2 = 9\times10 - \{99\} = 90 - 1 = 89$ cases

*$T_3 = 9\times 10\times 10 - \{99\}\times 10 - 9\times \{99\} = 900 - 10 - 9 = 881$ cases

*$T_4 =$ and here I mess up the cases that I can make

Of course the calculation for final number of outcomes is not necessary, but I am unable to understand how I can include/exclude cases for larger sequences :-(
Someone please help!
TIA!
 A: Since the title of your question talks about recursion, here is a recursive way of defining $T_n$:
Let $T_n^9$ be the number of $n$-digit numbers not containing $99$ and ending with $9$ and let $T_n^{\neg 9}$ be the number of $n$-digit numbers not containing $99$ and not ending with $9$.
Then we have the following recursive relations:

*

*$T_{n+1}^9 = T_n^{\neg 9}$ (an $n+1$ digit number ending with $9$ has to start with a $n$ digit number not ending with $9$ to avoid a $99$ at the end)

*$T_{n+1}^{\neg 9} = T_n \cdot 9$ (an $n+1$ digit number not ending with $9$ starts with any $n$ digit number (not containing $99$, of course) followed by one of the $9$ digits which are not $9$ (to avoid a $9$ at the end).

Of course, we also have $T_1^9 = 1$, $T_1^{\neg 9} = 8$ and $T_n = T_n^9 + T_n^{\neg 9}$.
As a sanity check:




$n$
$T_n^9$
$T_n^{\neg 9}$
$T_n$




1
1
8
1+8=9


2
8
$9\cdot 9=81$
8+81=89


3
81
$89\cdot 9 = 801$
81+801=882




which are exactly the numbers you got (including the correction by jjagmath)

Edit: And I just noticed that we can further simplyfy the recursion as follows:
$$T_{n+2} = T_{n+2}^9 + T_{n+2}^{\neg 9} = T_{n+1}^{\neg 9} + T_{n+1}\cdot 9 = T_n \cdot 9 + T_{n+1}\cdot 9 = 9\cdot(T_n + T_{n+1})$$
with initial terms $T_1 = 9$ and $T_2 = 89$.
Edit2: There is also a direct combinatorial argument of why the simpler recursion holds:
To get an $n+2$ digit number not containing a $99$ we can

*

*either take an $n+1$ digit number not containing a $99$ and add one of the digits $0,1,...,8$ at the end

*or take an $n$ digit number not containing a $99$ and add one of the digits $0,1,...,8$ followed by a $9$ at the end.

Now, it is easy to check that we really get all desired numbers this way and do not count any number twice :-)
