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.

• Start with an easier problem: how many two-digit numbers are there? what about three-digit? – Vasya Apr 18 at 18:42
• I could simply guess the case of two digit numbers. How does it help me prove the general one? – furfur Apr 18 at 18:53
• You do not need to guess, you can count. How many choices for the first digit do you have? what about the second? – Vasya Apr 18 at 19:08
• For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this. – furfur Apr 18 at 19:11
• Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}\qquad \text{for all }m\ge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it. – Mike Earnest Apr 18 at 20:30

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

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

• It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $\lambda^5-4\lambda^3+3\lambda=\lambda(\lambda^2-1)(\lambda^2-3)$, etc. – Mike Earnest Apr 18 at 20:12

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

• Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though! – furfur Apr 18 at 19:26