Counting problem about Palindromes Consider the set of four digit sequences $d_1d_2d_3d_4$, where $d_i\in\{0,1,\ldots,9\}$.
(a) What is the number of all four digit sequences, which contain no palindromic subsequence. For example, the sequence $1231$ is legal but $1213$ is not. We note that a subsequence such as $22$ is considered palindromic.
(b) Can the solution of this problem can be generalized easily for $n$-digits sequences?
My attempt: First we solve the problem for $3$-digits and then use the complement principle.

Let $F(n)$ be the number of $n$-digit sequences with this property.
For an $n+1$-digit sequence, $xabc...$, to have this property, we require $abc...$ to have the property (in which case $a\ne b$) and we then require $x\ne a$ and $x\ne b$.
Therefore, for $n\ge 2$, $F(n+1)=8F(n)$.
$F(2)=90$ and, for $n\ge 3$, $F(n)=90 \times8^{n-2}$.
