Recursive formula to find the number of natural numbers in which there are no two adjacent even digits. 
Need to find a Recursive formula that finds all the natural numbers (number can't start with a 0), in which there are no two adjacent even digits.
(For example: $13261$ is not a valid number because 2,6 are adjacent).

So if I look at the $A_n$ step in the recursion I can divide the problem into 2 ways:

*

*Case 1: $A_n= \text{odd}$ (valid number in size $n-1$).
In this case, the odd number has 5 options to choose from.


*Case 2: $A_n = \text{even, odd}$ (valid number in size $n-2$).
In this case, we have 4 options for the even number and 5 for the followed odd number.

So the recursive function that I've got is $A_n=5A_{n-1}+20A_{n-2}$
Is it correct ?

 A: Let us define our notation. Let $\,A_n\,$ count the positive numbers
with $\,n\,$ decimal digits such that no two adjacent digits are even.
Among the numbers counted by $\,A_n\,$ let $\,B_n\,$ count those numbers
which begin with an even digit and $\,C_n\,$ count those numbers which
begin with an odd digit. Thus $\,A_n = B_n + C_n\,$ by definition. Now
$\,B_n = 4 C_{n-1}\,$ because if a number begins with an even digit then
the next digit must be odd. Now $\,C_n = 5 A_{n-1} + 5 C_{n-2}\,$ because
if the first digit is odd and the second digit is not $0$ then we are in
the $\,A_{n-1}\,$ case and there are $5$ odd digits while if the second
digit is $0$ (which is even) then the next digit must be odd and we are in
the $\,C_{n-2}\,$ case. In the equation for $\,C_n\,$ substitute the other
two equations to get
$$ C_n = 5(B_{n-1} + C_{n-1} + C_{n-2}) = $$
$$ 5(4C_{n-2} + C_{n-1} + C_{n-2})
= 5C_{n-1} + 25C_{n-2}. $$
Now $\,B_n\,$ satisfies the same recursion. Since $\,A_n = B_n + C_n\,$
so does $\,A_n.$ The initial values are
$\, B_0 = 0,\; C_0 = 1,\; C_1 = 5.$
