This site is supported by donations to The OEIS Foundation.

# Fibonacci rabbits

There are a number of ways of keeping track of the population of "[male-female] pairs of Fibonacci rabbits" pertaining to the Fibonacci numbers.

## Tree of "[male-female] pairs of Fibonacci rabbits"

The Fibonacci rabbits tree (more precisely, the tree of [male-female] pairs of Fibonacci rabbits), named after Leonardo of Pisa (known as Fibonacci), follows the rules:

• at the beginning of the 0 th month, there are no rabbits on the island;
• at the beginning of the 1st month, a [male-female] pair of newborn rabbits is dropped on the island;
• thereafter, at the beginning of each month,
• every [male-female] pair of newborn rabbits becomes a [male-female] pair of mature rabbits,
• every [male-female] pair of mature rabbits begets a [male-female] pair of newborn rabbits, where the offspring stands to the right of the parents;

where

• a [male-female] pair of newborn rabbits (red vertex) is represented either by 0 (mature = FALSE, left side tree) or by an age equal to 0 month (right side tree);
• a [male-female] pair of mature rabbits (green vertex) is represented either by 1 (mature = TRUE, left side tree) or by an age greater than 0 month (right side tree);
• rabbits never die.
The number of rabbits at the beginning of each month gives the Fibonacci numbers (A000045
 (n), n   ≥   0
)
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, ...}
If any [male-female] pair of rabbits could beget a new [male-female] pair of rabbits, we would have 0 followed by
 2 n  −  1
pairs at the beginning of the
 n
th month (A131577
 (n), n   ≥   0
)
{0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, ...}
A131577
 (n)
@opsp@−@opsp@ A000045
 (n), n   ≥   0
, i.e. the number of non-existing [male-female] pair of rabbits due to the maturation delay (0 followed by A027934
 (n  −  1), n   ≥   1
)
{0, 0, 1, 2, 5, 11, 24, 51, 107, 222, 457, 935, 1904, 3863, 7815, 15774, 31781, 63939, 128488, 257963, 517523, 1037630, 2079441, 4165647, 8342240, 16702191, 33433039, ...}

### Binary sequence of "[male-female] pairs of Fibonacci rabbits"

The tree of newborn (0) and mature (1) "[male-female] pairs of Fibonacci rabbits" yields the binary sequence of "[male-female] pairs of Fibonacci rabbits"
 a(n), n   ≥   1,
(A036299
 (n  −  2), n   ≥   2
)
{0, 1, 10, 101, 10110, 10110101, 1011010110110, 101101011011010110101, 1011010110110101101011011010110110, 1011010110110101101011011010110110101101011011010110101, ...}
A005203 Fibonacci rabbits numbers (or rabbit sequence) converted to decimal,
 n   ≥   1
.
{0, 1, 2, 5, 22, 181, 5814, 1488565, 12194330294, 25573364166211253, 439347050970302571643057846, 15829145720289447797800874537321282579904181, ...}

### Sequence of "[male-female] pairs of Fibonacci rabbits"

The tree of newborn (0 month old) and mature (≥ 1 months old) "[male-female] pairs of Fibonacci rabbits" yields the infinite sequence of finite sequences

{{0}, {1}, {2, 0}, {3, 0, 1}, {4, 0, 1, 2, 0}, {5, 0, 1, 2, 0, 3, 0, 1}, {6, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0}, {7, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1}, ...}
whose concatenation yields the sequence of "[male-female] pairs of Fibonacci rabbits"
 a(n), n   ≥   1,
(A035614
 (n  −  1), n   ≥   1
)
{0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1, 6, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 7, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1, ...}

## Substitution rules

### Substitution rule for the binary sequence of "[male-female] pairs of Fibonacci rabbits"

The Fibonacci rabbits binary sequence (more precisely, the binary sequence of [male-female] pairs of Fibonacci rabbits) is defined by the initial conditions:

•  a(0) =
; (the empty string: there are no rabbits on the island)
•  a(1) = 0
; (a [male-female] pair of newborn rabbits is dropped on the island)
and the substitution rules, for
 n > 1
:
•  0 → 1
(a [male-female] pair of newborn rabbits becomes a [male-female] pair of mature rabbits);
•  1 → 10
(a [male-female] pair of mature rabbits begets a [male-female] pair of newborn rabbits, where the offspring stands to the right of the parents);

where

• a [male-female] pair of newborn rabbits is represented by 0 (i.e. mature = FALSE);
• a [male-female] pair of mature rabbits is represented by 1 (i.e. mature = TRUE).

### Substitution rule for the sequence of "[male-female] pairs of Fibonacci rabbits"

The Fibonacci rabbits sequence (more precisely, the sequence of [male-female] pairs of Fibonacci rabbits) is defined by the initial conditions:

•  a(0) =
; (the empty string: there are no rabbits on the island)
•  a(1) = 0
; (a [male-female] pair of newborn rabbits, i.e. 0 month old, is dropped on the island)
and the substitution rules, for
 n > 1
:
•  0 → succ(0)
where
 succ(0) = 1
is the successor of
 0
(a [male-female] pair of newborn rabbits becomes a [male-female] pair of mature rabbits, i.e. more than 0 month old);
•  k → succ(k), 0
for
 k   ≥   1
, where
 succ(k)
is the successor of
 k
(a [male-female] pair of mature rabbits begets a [male-female] pair of newborn rabbits, where the parent's age increases by 1 month, and where the offspring stands to the right of the parents).

## "[male-female] pairs of Fibonacci rabbits" per generation

The number of [male-female] pairs of Fibonacci rabbits per generation are expressed by the Fibonacci polynomials.

## The infinite Fibonacci word

A005614 The infinite Fibonacci word (start with 1, apply 0 -> 1, 1 -> 10, iterate, take limit).

{1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, ...}

## Properties

Theorem.

The
 n
th term,
 n   ≥   3
, of the binary Fibonacci rabbits sequence may be obtained by the concatenation of the
 (n  −  1)
th term and [appended by] the
 (n  −  2)
th term.

Proof. (by induction)

(Using . (dot) as the concatenation operator.)

Base case:
 a(1) = 0, a(2) = 1
and
 a(3) = 10 = 1 . 0 = a(2) . a(1)
;

Inductive step:

Assume the truth of
 a(k) = a(k  −  1) . a(k  −  2)
for
 3   ≤   k   ≤   n  −  1
;
then we have to show that this implies
 a(n) = a(n  −  1) . a(n  −  2)
...

Thus, using . (dot) as the concatenation operator

${\displaystyle a(n)=a(n-0)\,}$
${\displaystyle a(n)=a(n-1)\,.\,a(n-2)\,}$
${\displaystyle a(n)=a(n-2)\,.\,a(n-3)\,.\,a(n-3)\,.\,a(n-4)\,}$
${\displaystyle a(n)=a(n-3)\,.\,a(n-4)\,.\,a(n-4)\,.\,a(n-5)\,.\,a(n-4)\,.\,a(n-5)\,.\,a(n-5)\,.\,a(n-6)\,}$
...

which suggests the infinite sequence of finite sequences

{{0}, {1, 2}, {2, 3, 3, 4}, {3, 4, 4, 5, 4, 5, 5, 6}, {4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}, {5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10}, ...}

whose concatenation gives (matches (proof?) A014701 Number of multiplications to compute n-th power by method of Chandra-sutra.)

{0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10, ...}

Equivalently

${\displaystyle a(n)=a(n-1)\,2^{1+\lfloor \log _{2}(a(n-2))\rfloor }+a(n-2)=a(n-1)\,2^{F(n-2)}+a(n-2),\quad n\geq 2.\,}$

## Asymptotic behavior

${\displaystyle {\frac {a(n)}{a(n-1)}}\sim 2^{F(n-2)}\sim 2^{\{{\frac {\phi ^{n-2}}{\sqrt {5}}}\}}\,}$
${\displaystyle a(n)\sim a(n-1)\,2^{F(n)-F(n-1)}\,}$
${\displaystyle a(n)\,2^{F(n-1)}\sim a(n-1)\,2^{F(n)}\,}$
${\displaystyle a(n)\,2^{\{{\frac {\phi ^{n-1}}{\sqrt {5}}}\}}\sim a(n-1)\,2^{\{{\frac {\phi ^{n}}{\sqrt {5}}}\}}\,}$
${\displaystyle \{a(n)\}^{\sqrt {5}}\,2^{\{\phi ^{n-1}\}}\sim \{a(n-1)\}^{\sqrt {5}}\,2^{\{\phi ^{n}\}}\,}$