How many odd $100$-digit numbers such that every two consecutive digits differ by exactly 2 are there? How many odd $100$-digit numbers such that every two consecutive digits differ by exactly 2 are there?
My first idea was to calculate the number of all odd $100$-digit numbers which use only odd digits, which equals $5^{100}$, and then try to subtract the number of all bad numbers, but I couldn't calculate it.
Then I tried to establish recurrence relation, but I don't even know where to start.
For example, all $3$-digit numbers which satisfy above condition: $135$, $131$, $313$, $353$, $357$, $535$, $531$, $575$, $579$, $757$, $753$, $797$, $975$, $979$ .
Please help!
 A: To establish a recurrence relation you could proceed as follows (this is an answer not a comment for length, but won't solve the recurrence).
Let $a_n, b_n, c_n, d_n, e_n$ be respectively the number of $n$-digit numbers in your set beginning with the digits $1,3,5,7,9$ respectively. Then stripping the first digit gives $$a_n=b_{n-1}; b_n=a_{n-1}+c_{n-1}; c_n=b_{n-1}+d_{n-1};d_n=c_{n-1}+e_{n-1};e_n=d_{n-1}$$
Then observe that symmetry considerations give $a_n=e_n$ and $b_n=d_n$
This reduces the system to $3$ equations $$a_n=b_{n-1}$$$$ b_n=a_{n-1}+c_{n-1}$$$$ c_n=2b_{n-1}$$ and that immediately gives $c_n=2a_n$ and I'll leave it to you to solve from there, having got the system under some control.
A: A direct recurrence is difficult, but if we count something different, then it becomes easier. For each of the five digits $d \in \{1,3,5,7,9\}$, and for each number length $n$, we can count the number $A(d,n)$ of numbers satisfying your constraint. For each $d$, we have $A(d,1) = 1$. For $n > 1$, we have $A(n,1) = A(n-1,3)$, and $A(n,9) = A(n-1,7)$, and for the other digits $d$, we have
$$
A(n,d) = A(n-1,d-2) + A(n-1,d+2).
$$
This is still tedious for a human to compute, but a very short computer program should make this easy.
A: Define $D(n, e)$ as your number, length $n$ and ending with $e$.
$D(1, e) = 1, e \in \{1,3,5,7,9\}$
$D(n, 1) = D(n, 9) = D(n-1, 3)$
$D(n, 3) = D(n, 7) = D(n-1, 5) + D(n-1, 1)$
$D(n, 5) = D(n-1, 3) + D(n-1, 7) = 2*D(n-1, 3)$
A: Let $t_n$ be the number of good sequences of length $n$.  for $d\in \{1,3,5,7,9\}$ let $d_n$ denote the number of good sequences that end in $d$.  recursively"
$$1_n=3_{n-1}\quad 3_n=1_{n-1}+5_{n-1}\quad  \cdots \quad 9_n=7_{n-1}$$
This is easy to implement, and we get $t_3=14$, $t_{100}=1914394633844940236720664 $.
the first few values are $\{5,8,14,24,42,72,126,\dots\}$ which is not recognized by OEIS...I doubt there is a pleasant closed formula for them. 
Note:  As remarked by @MarkBennet below, there is indeed a pleasant closed formula for these number, my doubts notwithstanding.  This follows from the symmetry considerations well described in his posted solution. 
