How many 20-digit numbers can be formed from {1,2,3,4,5,6,7,8,9} such that no 2 consecutive digit is both odd How many 20-digit numbers can be formed from {${1,2,3,4,5,6,7,8,9}$} such that no 2 consecutive digit is both odd. (Repetition allowed)
I've noticed that the number of odd digit in the number must be less than 11. But i can't progress more than that.
Any help is appreciated. Thanks in advance.

Hint. Let $x_n$ be the number of $n$-digit numbers which can be formed from $\{1,2,3,4,5,6,7,8,9\}$ such that no two consecutive digits are both odd.
We split $x_n$ into two parts: $a_n$ counts the numbers where the last digit is odd and $b_n$ counts the ones where the last digit is even. Then $x_n=a_n+b_n$.
Moreover we can easily check that $a_1=5$, $b_1=4$, $a_2=4\cdot 5=20$, $b_2=9\cdot4=36$.
Is there any recurrences which involve $a_n$, $b_n$, $a_{n+1}$ and $b_{n+1}$?
Can you take it from here?
