How many 20-digit numbers can be formed from <mo fence="false" stretchy="false">{ 1 , 2

How many 20-digit numbers can be formed from $\left\{1,2,3,4,5,6,7,8,9\right\}$ such that no 2 consecutive digit is both odd
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.
You can still ask an expert for help

Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Freddy Doyle
Step 1
Let ${x}_{n}$ be the number of n-digit numbers which can be formed from $\left\{1,2,3,4,5,6,7,8,9\right\}$ 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}$.
Step 2
Moreover we can easily check that ${a}_{1}=5$, ${b}_{1}=4$, ${a}_{2}=4\cdot 5=20$, ${b}_{2}=9\cdot 4=36$.
Is there any recurrences which involve ${a}_{n}$, ${b}_{n}$, ${a}_{n+1}$ and ${b}_{n+1}$?