5

Consider the rabbit Fibonacci problem. We start with one young rabbit couple. At each step, young rabbit couple grows to adult rabbits and adult rabbit couples give birth a young couple. If we denote A for an adult couple and y for a young couple, we do iteratively A$\to$Ay, y$\to$A and the sequence is :

y
A
Ay
AyA
AyAAy
AyAAyAyA
AyAAyAyAAyAAy
AyAAyAyAAyAAyAyAAyAyA
AyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAy
AyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAyA
AyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAy
AyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAAyAyAAyAyAAyAAyAyAAyAyA

Quite funnily, except for the first, y, if the $k$th couple is adult (resp. young), is will stay adult (resp. young) forever (despise the shift due to A$\to$Ay ).

For now, having this fact empirically is enough for me. My question is : is there a simple way to know whether the $k$th couple of the sequence, if it exists, is an adult couple or a young couple, without iterating back the whole sequence ?

Thank you.

Lærne
  • 2,515
  • It's not so difficult to show that the sequence is stable the way you describe it via induction on the position in the sequence (i.e. show that after the first time the $k$th letter is assigned either A or y, it will never change, rather than that the $k$th word will always begin with the $(k-1)$th word). – Arthur Sep 25 '17 at 11:15
  • Iterating over the position instead of the Fibonacci numbers ? Smart. – Lærne Sep 25 '17 at 11:57

1 Answers1

3

This OEIS entry gives the formula* $$ r_k = \lfloor(k+1)\phi\rfloor-\lfloor k\phi\rfloor - 1 $$ where $\phi = \frac{\sqrt 5 - 1}{2}$ is the golden ratio. To translate into your language, $1$ in the OEIS sequence means A, and $0$ means y. The first A corresponds to $r_1$.

*The formula as given in the OEIS doesn't have the $-1$ term at the end, and yields $1$ and $2$, while the sequence has $0$ and $1$. Alternatively, one could've swapped out $\phi$ with $\phi' = \frac1\phi = \phi-1$ instead of appending $-1$.

Arthur
  • 199,419