# Estimate of the number of rabbit integers with a given congruence

Consider the Fibonacci words $B_n$:

• $B_1 = 1$
• $B_2 = 10$
• $B_3 = 101$
• $B_4 = 10110$
• $B_5 = 10110101$

(start with $B_1=1$, and go from $B_n$ to $B_{n+1}$ by replacing every occurence of $1$ in $B_n$ with $10$ and every occurence of $0$ with $1$).

The word $B_n$ has $f_n$ digits, the $n$-th Fibonacci number.

For a given integer $\alpha \geq 2$ and $0 \leq j < \alpha$, denote by $$R_n(\alpha,j) = \#\bigl\{1 \leq i \leq f_n \mid B_n(i)=1 \,\text{ and }\, i\!\!\!\!\pmod\alpha=j \bigr\}$$ the number of integers $i$ in $\{1, \ldots, f_n\}$ such that $i$ is a "rabbit integer" (I mean $B_n(i)=1$) and $i$ is congruent to $j$ modulo $\alpha$.

Does one know an asymptotic estimate of $R_n(\alpha,j)$ when $n \to \infty$ ?

• You index Fibonacci numbers so that $f_2=2$? – Douglas Zare Jan 18 '16 at 17:11
• @DouglasZare I take $f_0=f_1=1$. Is it important ? – Stéphane Laurent Jan 18 '16 at 17:12
• I don't think it is important here, but I think it is also not the usual convention. – Douglas Zare Jan 18 '16 at 17:13
• So you ask what is known about the "Lower Wythoff sequence" oeis.org/A000201 modulo an integer $\alpha$. – Wolfgang Jan 18 '16 at 17:23
• The books I'd suggest are iml.univ-mrs.fr/editions/preprint00/book/prebookdac.html, Substitutions in Dynamics, Algorithms and Combinatorics; and Queffélec's book, Substitution Dynamical Systems: Spectral Analysis. In the meantime, Douglas Zare's answer below gives a straightforward answer to your specific question. – Anthony Quas Jan 18 '16 at 19:27

One way to describe this sequence is the indices where $\lfloor (n+1) \phi \rfloor \gt \lfloor n \phi \rfloor$, or equivalently when $n \phi \mod 1$ is in a particular interval of length $1/\phi$, namely $[1-1/\phi,1)$. Your subsequences with indices in an arithmetic progression correspond to when $(\alpha n + j) \phi = n (\alpha \phi) + j \phi$ is in that interval mod $1$, or equivalently when $n(\alpha \phi)$ is in a translated interval. For any positive integer $\alpha,$ $\alpha \phi$ is irrational, so the multiples are equidistributed and they hit the interval with density $1/\phi$.
This tells you that $$\lim_{n\to \infty} \frac{R_n(\alpha,j)}{|B_n|} = \frac{1}{\alpha \phi}$$ but it might be possible to get good estimates on $|B_n| - \alpha \phi R_n(\alpha,j)$.