Fibonacci rabbits

This article needs more work.

Please help by expanding it!

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"

Tree of newborn (0) and mature (1) "[male-female] pairs of Fibonacci rabbits" 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1

Tree of newborn (0 months old) and mature (≥ 1 months old) "[male-female] pairs of Fibonacci rabbits" 0 1 2 0 3 0 1 4 0 1 2 0 5 0 1 2 0 3 0 1

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 1^st 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

$a(n)=a(n-0)\,$

$a(n)=a(n-1)\,.\,a(n-2)\,$

$a(n)=a(n-2)\,.\,a(n-3)\,.\,a(n-3)\,.\,a(n-4)\,$

$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

$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

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

$a(n)\sim a(n-1)\,2^{F(n)-F(n-1)}\,$

$a(n)\,2^{F(n-1)}\sim a(n-1)\,2^{F(n)}\,$

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

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

External links

• The Golden String of 0s and 1s, © 1996-2011 Dr Ron Knott.
• Weisstein, Eric W., Rabbit Sequence, from MathWorld—A Wolfram Web Resource.