Combinatorics problem on counting. How many positive integers n are there such that all of the following take place:
1) n has 1000 digits.
2) all of the digits are odd.
3) the absolute value of the difference of any two consecutive (neighboring) digits is equal to 2.
Please help. I don’t even know how to start.
 A: The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boils down to a very simple final answer for $n\ge2$: $$a_n=\begin{cases}\hphantom18\cdot 3^{\frac{n-2}2},& n\text{ even},\\14 \cdot 3^{\frac{n-3}2},& n\text{ odd}.\end{cases}\tag1$$
The simplest approach to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia:
$$
a_n=4a_{n-2}-3a_{n-4}.\tag2
$$ 
In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.
A: Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9).
Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and  $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.
Edit:
We have $$A=\left(\begin{array}{ccccc}
 0&1&0&0&0\\
 1&0&1&0&0\\
 0&1&0&1&0\\
 0&0&1&0&1\\
 0&0&0&1&0\\
\end{array}
\right)$$
So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with 
$$D=\left(\begin{array}{ccccc}
 -1&0&0&0&0\\
 0&0&0&0&0\\
 0&0&1&0&0\\
 0&0&0&-\sqrt{3}&0\\
 0&0&0&0&\sqrt{3}\\
\end{array}
\right)$$
$$P=\left(\begin{array}{ccccc}
 -1&1&-1&1&1\\
 1&0&-1&-\sqrt{3}&\sqrt{3}\\
 0&-1&0&2&2\\
 -1&0&1&-\sqrt{3}&\sqrt{3}\\
 1&1&1&1&1\\
\end{array}
\right)$$
So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-\sqrt{3})^{999},(\sqrt{3})^{999}$. 
A: Here is a OCaml program that computes the number of numbers in term of the size of the number:
type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)


let hdStr (s: 'a stream) : 'a =
  match s with
  | Eos -> failwith "headless stream"
  | StrCons (x,_) -> x;;

let tlStr (s : 'a stream) : 'a stream =
  match s with
  | Eos -> failwith "empty stream"
  | StrCons (x, t) -> t ();;    



let rec listify (s : 'a stream) (n: int) : 'a list =
  if n <= 0 then []
  else
    match s with
    | Eos -> []
    | _ -> (hdStr s) :: listify (tlStr s) (n - 1);;

let rec howmanynumber start step=
  if step = 0 then 1 else
    match start with
    |1->howmanynumber 3 (step-1)
    |3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
    |5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
    |7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
    |9->howmanynumber 7 (step-1) 
    |_->failwith "exception error"



let count n=
  (howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)

let rec thisseq  n = StrCons(count n , fun ()-> thisseq (n+1))

let result = thisseq 1

So Based on @Julian solution, the answer is the sum of entries of 
$\begin{bmatrix}
0       & 1 & 0 & 0 & 0 \\
1       & 0 & 1 & 0 & 0 \\
0       & 1 & 0 & 1 & 0 \\
0       & 0 & 1 & 0 & 1\\
0       & 0 & 0 & 1 & 0 \\
\end{bmatrix}^{999} * \begin{bmatrix}
1        \\
1      \\
1       \\
1       \\
 1       \\
\end{bmatrix}$
