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.

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