0
$\begingroup$

Are there references in the literature that deal with the probability of finding an integer sequence in a linear homogeneous recurrence with constant coefficients $ \in \mathbb{Z}$? (or provides a way to count them?). If the linear recurrence is given by $$\sum_{k=0}^{d}a_kx_{n+k}=0 \quad (x_0,...,x_{d-1})=(b_0,.., b_{d-1}) \in \mathbb{Z} \; \forall \;b_{i} \quad n \in \mathbb{N}_{0} $$ Are there references for the following probability or cardinal? $$P(\textrm{drawing (uniformly) random}\;a_{k}\; \textrm{with} -m\leq a_{k}\leq m\;: \; x_{n} \in \mathbb{Z} \;\;\forall n \in \mathbb{N}_{0})$$ $$\#\{-m\leq a_{k}\leq m, \; a_{k} \in \mathbb{Z}: x_{n} \in \mathbb{Z} \;\;\forall n \in \mathbb{N}_{0} \}$$

The closest research I have found is related to generate Binet's formulas for recurrences of degree $d$ and this paper of Pemantle and Wilf for general bounded non-decreasing integer sequences. But I haven't seen the specific question before.

Improve this question
$\endgroup$
3
  • $\begingroup$ So the question is: if we fix the $b_i$, how many assignments of the $a_i$ give integer values for all positive and negative $n$? $\endgroup$
    – Peter Taylor
    Commented Jul 30, 2021 at 10:07
  • $\begingroup$ Yes, exactly that, but $n$ natural greater or equal than 0. I fix it in the post. $\endgroup$
    – rgvalenciaalbornoz
    Commented Jul 30, 2021 at 10:15
  • $\begingroup$ Just in case, for recurrences of degree $1$, $a_{1}x_{n+1}+a_{0}x_{n}=0,x_{0}=b_{0}$, the result is trivial, since the mentioned probability is related to the probability that $a_{1}|a_{0}$ from a set of $(2m)^2$ pairs, which is roughly $\frac{log(2m)}{2m}$ $\endgroup$
    – rgvalenciaalbornoz
    Commented Jul 30, 2021 at 10:29

0

Reset to default

You must log in to answer this question.