2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You index Fibonacci numbers so that $f_2=2$? $\endgroup$ – Douglas Zare Jan 18 '16 at 17:11
  • $\begingroup$ @DouglasZare I take $f_0=f_1=1$. Is it important ? $\endgroup$ – Stéphane Laurent Jan 18 '16 at 17:12
  • $\begingroup$ I don't think it is important here, but I think it is also not the usual convention. $\endgroup$ – Douglas Zare Jan 18 '16 at 17:13
  • 1
    $\begingroup$ So you ask what is known about the "Lower Wythoff sequence" oeis.org/A000201 modulo an integer $\alpha$. $\endgroup$ – Wolfgang Jan 18 '16 at 17:23
  • 4
    $\begingroup$ 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. $\endgroup$ – Anthony Quas Jan 18 '16 at 19:27
7
$\begingroup$

You are asking about subsequences of the infinite Fibonacci word A005614.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.