How to find a recursive formula for the number of combinations of {1, ...., 9} of length n, such that there are no uneven digits next to each other?

Question

I can't figure out how to formulate this in a single expression as the number of options for each additional digit depends on the previous last digit's value, but each previous step represents the number of combinations, not a specific number.

Also, I would like to know the correct way to compute this directly, and not recursively.

Thanks!

Answer 1

So I'd like to implement my comment as an answer.
Let f(number of even digits taken,number of odd digits taken,is last digit even) be the recursive function with initial conditions $f(1,0,1)=4$,$f(0,1,0)=5$,$f(1,0,0)=0$,$f(0,1,1)=0$.
Now, for $m>0,n>0$ we get
$f(m,n,1)=\left(f(m-1,n,1)+f(m-1,n,0)\right)\cdot(4-(m-1))$,
$f(m,n,0)=f(m,n-1,1)\cdot(5-(n-1))$.
And $g(x)=\sum\limits_{m+n=x\\0\le m\le4\\0\le n\le5} (f(m,n,1)+f(m,n,0))$ will give the desired result.
As we have only $6$ values for $m$ and only $5$ values for $n$, the $f$ table will consist of $6\cdot 5\cdot 2=60$ values, not too much to do by hand.
If done right, the table will be similar to this:

               f(m,n,1)           |           f(m,n,0)           
       m=0   m=1   m=2   m=3   m=4|   m=0   m=1   m=2   m=3   m=4
n=0      1     4    12    24    24|     1     0     0     0     0
n=1      0    20   120   360   480|     5    20    60   120   120
n=2      0     0   240  1440  2880|     0    80   480  1440  1920
n=3      0     0     0  1440  5760|     0     0   720  4320  8640
n=4      0     0     0     0  2880|     0     0     0  2880 11520
n=5      0     0     0     0     0|     0     0     0     0  2880

(source code)

Answer 2

We have to count the number of admissible words $w$ of length $n\geq0$ over the alphabet $[9]$, meaning that $w$ should not contain two consecutive odd numbers. Let $a_n$ be the number of such words.

Fix $n\geq2$. An admissible word $w$ of length $n$ either (a) ends with an even digit or (b) with an odd digit. In case (a) this $w$ is generated by appending an even digit to an arbitrary admissible word of length $n-1$. The number of such $w$s is $\>a_{n-1}\cdot4$, because there are $4$ even digits in the alphabet. In case (b) the $n$th (odd) digit has to be preceded by an even digit. It follows that this $w$ is generated by appending first an even digit to an arbitrary admissible word of length $n-2$, and then an odd digit. The number of such $w$s therefore is $a_{n-2}\cdot4\cdot5$. Together we obtain the recursion $$a_0=1,\quad a_1=9,\qquad a_n=4a_{n-1}+20 a_{n-2}\quad(n\geq2)\ .$$ The obtained recursion is a linear difference equation with constant coefficients. Standard techniques (called "Master Theorem" by some) allow to obtain a closed formula for the $a_n$.