Mryntu

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(beginarrayccccc
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\
endarray
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(beginarrayccccc
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt3&0\
0&0&0&0&sqrt3\
endarray
right)$$

$$P=left(beginarrayccccc
-1&1&-1&1&1\
1&0&-1&-sqrt3&sqrt3\
0&-1&0&2&2\
-1&0&1&-sqrt3&sqrt3\
1&1&1&1&1\
endarray
right)$$
So, we can compute $A^999=PD^999P^-1$ whose entries will be a linear combination of $(-1)^999, (1)^999, (-sqrt3)^999,(sqrt3)^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

$beginbmatrix
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 \
endbmatrix^999 * beginbmatrix
1 \
1 \
1 \
1 \
1 \
endbmatrix$

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=begincaseshphantom18cdot 3^fracn-22,& ntext even,\14 cdot 3^fracn-32,& ntext odd.endcasestag1$$

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