# 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$ .

• Can you please give example of one such number? – tatan Oct 12 '16 at 11:28
• Sorry, I forgot. All $3$-digit numbers which satisfy above condition: $135$, $131$, $313$, $353$, $357$, $535$, $531$, $575$, $579$, $757$, $753$, $797$, $975$, $979$ . – mivan Oct 12 '16 at 11:30
• I take it you mean "differ in absolute value"? So $202020\dots$ is a good example? – lulu Oct 12 '16 at 11:30
• @tatan For instance, $13135753$, or $64246864$ for $8$ digits. It's like a bounded random walk. – Jean-Claude Arbaut Oct 12 '16 at 11:31
• Can you please clarify your question? The number of odd $100$-digit numbers is NOT $5^{100}$. And then you switch to three digits, which can easily be done by hand... – lulu Oct 12 '16 at 11:32

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 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.

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)$

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.

• After the first few terms each is three times the term two before it. – Mark Bennet Oct 12 '16 at 11:51
• @MarkBennet True...not immediately sure why, though. – lulu Oct 12 '16 at 12:02
• @MarkBennet Ah, symmetry does it. But I see you've covered that in your solution. – lulu Oct 12 '16 at 12:08