Ttyjukl

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

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

The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $nge2$: $$a_n=begin{cases}hphantom18cdot 3^{frac{n-2}2},& ntext{ even},\14 cdot 3^{frac{n-3}2},& ntext{ odd}.end{cases}tag1$$

The most simple way 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)$.